/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2013 Spectra Logic.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * Verify the integrity of non-aligned writes to the same blocks within the same
 * transaction group, where an fsync is issued by a non-final writer.
 *
 * This test verifies that the unoverride in the following sequence of events is
 * handled correctly:
 *
 * 1) A new transaction group opens
 * 2) A write is issued to a certain block
 * 3) The writer fsyncs() that file
 * 4) TBD module immediately writes that block, then places an override in the
 *    syncer's TBD data structure, indicating that it doesn't need to write that
 *    block when syncing.
 * 5) Another write is issued to the same block, with different data.
 * 6) TBD module unoverrides that block in the syncer's TBD data structure
 * 7) The syncer writes that block 
 *
 * Outline:
 *   Create a big zero-filled file.
 *   Create a bunch of different IO patterns.  Each IO pattern consists of:
 *   * A partition of the file range into 64 different non-overlapping chunks.
 *   * A permutation of those chunks
 *   For each repetition:
 *     For each IO pattern:
 *       Create one binary semaphore per chunk, per (n-1) threads
 *       Create n threads.
 *       The first thread will write each chunk in order.  It will post a
 *         semaphore after each write to indicate that it has completed 
 *         writing that chunk.
 *       The second thread will pend on those semaphores in order.  Each time it
 *         receives a semaphore, it will write a different pattern to that
 *         chunk.  Then it will post a different semaphore to signal the next
 *         thread.
 *       The final thread will not post any semaphores
 *       Every even-numbered thread, starting with the first (0th), will fsync()
 *         the file after its write.  The final thread, being odd-numbered,
 *         won't.
 *       Join all threads
 *       Read the entire file and verify that
 *         1)  Every write went to the correct location
 *         2)  The final thread's write is left in the file
 */

#include <stdint.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <errno.h>
#include <semaphore.h>
#include <pthread.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include <sys/mman.h>
#include <assert.h>
#include <arpa/inet.h>

#define NUM_REPETITIONS 16
#define CLUSTERSIZE (1 << 17)
#define NUM_CHUNKS 64
#define FSIZE  (64 * (CLUSTERSIZE)) //FSIZE may range from NUM_CHUNKS clusters to 8GB
#define USE_THREADS 1
#define NUM_THREADS 8

typedef struct {
  //partitions describes the boundaries between chunks.  Each element is a
  //fraction of the filesize in 1.31 fixed point format.  So the boundary 
  //between chunk n and chunk n-1 is (FSIZE * partitions[n-1] / (1<<31) .
  //partitions[-1] is understood to be 0 and partitions[NUM_CHUNKS] must be 1.0
  //partitions is sorted, of course.  
  //Partition boundaries must be dword aligned.  Thus, in order to work with 
  //multiple values of FSIZE, partitions values must be aligned to multiples of
  //8 / (NUM_CHUNKS * CLUSTERSIZE) = 1 / 524288 = 0x0.00002
  uint32_t partitions[NUM_CHUNKS]; 
  int permutation[NUM_CHUNKS];  //the order in which to write the chunks
} pattern_t;

typedef struct {
        int thread_num;
        const pattern_t* pat;
} thread_data_t;


/* Returns (via begin and end) the range of a chunk.  Begin is inclusive,
 * end is exclusive */
void get_chunk_range(const pattern_t* pat, int chunk, uint32_t* begin, uint32_t* end){
  if (chunk == 0){
    *begin = 0;
  }
  else{
    *begin = (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk - 1] >> 31);
  }
  *end =  (uint32_t)((uint64_t)FSIZE * (uint64_t)pat->partitions[chunk] >> 31);
}


/* The most basic, trivial IO pattern.  Fully sequential, and the follower
 * writes every other block */
const pattern_t trivial_pattern = {
  {0x2000000, 0x4000000, 0x6000000, 0x8000000, 0xa000000, 0xc000000, 0xe000000, 0x10000000, 
   0x12000000, 0x14000000, 0x16000000, 0x18000000, 0x1a000000, 0x1c000000, 0x1e000000, 0x20000000, 
   0x22000000, 0x24000000, 0x26000000, 0x28000000, 0x2a000000, 0x2c000000, 0x2e000000, 0x30000000, 
   0x32000000, 0x34000000, 0x36000000, 0x38000000, 0x3a000000, 0x3c000000, 0x3e000000, 0x40000000, 
   0x42000000, 0x44000000, 0x46000000, 0x48000000, 0x4a000000, 0x4c000000, 0x4e000000, 0x50000000, 
   0x52000000, 0x54000000, 0x56000000, 0x58000000, 0x5a000000, 0x5c000000, 0x5e000000, 0x60000000,
   0x62000000, 0x64000000, 0x66000000, 0x68000000, 0x6a000000, 0x6c000000, 0x6e000000, 0x70000000,
   0x72000000, 0x74000000, 0x76000000, 0x78000000, 0x7a000000, 0x7c000000, 0x7e000000, 0x80000000},
  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 
    32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 
    48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63}, 
};

//The below patterns were randomly generated
const pattern_t pat0 = {
  { 0x1eac000,  0x88a4000,  0xaffe000,  0xcdb7000,  0xd2d5000,  0xe16f000,  0xe499000,  0x11f71000,  0x1242d000,  0x12c07000,  0x143bc000,  0x1460a000,  0x15dd7000,  0x1700e000,  0x1be7e000,  0x1e14d000,  0x1e6ac000,  0x21097000,  0x24b74000,  0x27166000,  0x27669000,  0x30539000,  0x3218b000,  0x37591000,  0x37b60000,  0x39818000,  0x39d08000,  0x3c90e000,  0x3e54f000,  0x3fb99000,  0x42c8e000,  0x43a62000,  0x43f50000,  0x4c0c9000,  0x4c422000,  0x4c737000,  0x4d41e000,  0x4d738000,  0x4da71000,  0x4f4e8000,  0x508e3000,  0x51396000,  0x51ab5000,  0x52a02000,  0x54238000,  0x54d6a000,  0x55029000,  0x5584b000,  0x5c42c000,  0x5c4a7000,  0x5dac5000,  0x5fe4d000,  0x63f86000,  0x66ad0000,  0x67b3d000,  0x69ce5000,  0x6c179000,  0x6e79e000,  0x6f83f000,  0x71165000,  0x72bd9000,  0x7ac79000,  0x7dc94000,  0x80000000,    },
  { 57,  16,  28,  25,  10,  59,  52,  46,  30,  6,  40,  36,  39,  9,  21,  51,  33,  45,  44,  19,  2,  50,  55,  5,  58,  13,  23,  0,  12,  53,  42,  32,  31,  48,  35,  61,  49,  54,  18,  24,  8,  41,  62,  4,  47,  17,  1,  3,  34,  14,  63,  22,  15,  26,  38,  56,  27,  60,  29,  11,  7,  43,  20,  37,    },
};
const pattern_t pat1 = {
  { 0x2b5000,  0x16db000,  0x5eb5000,  0x93a0000,  0xa7cb000,  0xa9e9000,  0xd144000,  0xe7c2000,  0xeb7d000,  0x10919000,  0x10cbd000,  0x11f85000,  0x17360000,  0x1760a000,  0x18eab000,  0x1ae6b000,  0x1c5f6000,  0x1df38000,  0x21bec000,  0x239d1000,  0x26b81000,  0x2747b000,  0x27a03000,  0x2b3cc000,  0x2cbf9000,  0x2ec0f000,  0x30a68000,  0x30bea000,  0x30c64000,  0x311af000,  0x35823000,  0x35d23000,  0x3b20e000,  0x405d8000,  0x414c8000,  0x43a91000,  0x44049000,  0x4ab4e000,  0x4ae21000,  0x4d293000,  0x511e5000,  0x516fc000,  0x52d77000,  0x57229000,  0x5da57000,  0x5dbe6000,  0x6070e000,  0x60fc0000,  0x64b24000,  0x67636000,  0x67658000,  0x6b040000,  0x6b28f000,  0x6e551000,  0x707c0000,  0x71b5c000,  0x72062000,  0x762a1000,  0x788a0000,  0x7a1e1000,  0x7b06a000,  0x7e04c000,  0x7f4cf000,  0x80000000,    },
  { 45,  8,  55,  9,  21,  54,  41,  7,  6,  22,  31,  47,  23,  11,  48,  53,  0,  61,  63,  50,  17,  27,  12,  19,  10,  40,  14,  51,  39,  59,  2,  43,  18,  42,  52,  28,  16,  44,  3,  5,  15,  35,  58,  33,  57,  49,  34,  30,  46,  4,  37,  60,  32,  36,  25,  56,  24,  13,  20,  38,  29,  26,  62,  1,    },
};
const pattern_t pat2 = {
  { 0x912d000,  0xe610000,  0xf755000,  0x116df000,  0x128e5000,  0x1bd51000,  0x24e9a000,  0x27643000,  0x28cf4000,  0x292c9000,  0x2c907000,  0x2d389000,  0x2d941000,  0x2eb3f000,  0x30e94000,  0x31738000,  0x3343b000,  0x342ce000,  0x34d12000,  0x3536d000,  0x35e1a000,  0x35e4d000,  0x35fd5000,  0x3642b000,  0x3924d000,  0x392a5000,  0x3e531000,  0x3f0ee000,  0x3fdf8000,  0x41593000,  0x41c80000,  0x43959000,  0x43bc0000,  0x461c8000,  0x48922000,  0x49519000,  0x4f6fa000,  0x50274000,  0x508ae000,  0x536ed000,  0x54154000,  0x59894000,  0x5a666000,  0x5b0a6000,  0x5b9ff000,  0x5c109000,  0x5d8d0000,  0x5ddc5000,  0x5fcc5000,  0x63366000,  0x63adc000,  0x645b6000,  0x670eb000,  0x6b1b1000,  0x6c996000,  0x6ed2a000,  0x6ee4f000,  0x71fcd000,  0x734a3000,  0x76bdf000,  0x77b3f000,  0x7c65a000,  0x7d200000,  0x80000000,    },
  { 31,  35,  36,  52,  27,  56,  40,  13,  51,  49,  43,  37,  62,  42,  24,  29,  48,  25,  7,  61,  22,  57,  11,  32,  2,  54,  41,  6,  55,  15,  20,  26,  63,  44,  12,  4,  19,  58,  60,  59,  47,  23,  30,  50,  53,  34,  9,  38,  45,  8,  28,  3,  16,  33,  5,  21,  1,  10,  46,  18,  0,  14,  39,  17,    },
};
const pattern_t pat3 = {
  { 0x553000,  0x19de000,  0x6a20000,  0x8a53000,  0x8ef9000,  0xc325000,  0x1132e000,  0x139fa000,  0x1426b000,  0x150ff000,  0x1bbc1000,  0x1e84c000,  0x1f43e000,  0x1f731000,  0x21ec8000,  0x231f4000,  0x23440000,  0x23466000,  0x260b6000,  0x286a7000,  0x29518000,  0x29e35000,  0x2fdb7000,  0x3089d000,  0x362e0000,  0x3c1f9000,  0x3df2d000,  0x3fce6000,  0x402f3000,  0x4117f000,  0x41e06000,  0x4374f000,  0x451e5000,  0x45a59000,  0x4956b000,  0x4960f000,  0x4a934000,  0x4bc6f000,  0x4d462000,  0x4eef8000,  0x4f609000,  0x50dc1000,  0x51022000,  0x54396000,  0x5641b000,  0x578f1000,  0x589cf000,  0x59093000,  0x5da6b000,  0x5fbf0000,  0x605a2000,  0x65428000,  0x65530000,  0x6705a000,  0x6db65000,  0x71cef000,  0x725a2000,  0x73bf5000,  0x75acb000,  0x76065000,  0x7614c000,  0x77aab000,  0x78f70000,  0x80000000,    },
  { 15,  30,  31,  16,  49,  13,  55,  59,  4,  24,  26,  44,  17,  0,  18,  54,  10,  3,  46,  34,  29,  22,  45,  5,  38,  32,  39,  50,  48,  53,  12,  25,  35,  56,  51,  52,  1,  33,  43,  63,  47,  37,  23,  20,  60,  14,  11,  21,  8,  57,  27,  41,  6,  58,  62,  2,  19,  61,  28,  36,  40,  7,  9,  42,    },
};
const pattern_t pat4 = {
  { 0x425000,  0x8e8000,  0x4b90000,  0x883c000,  0x968e000,  0xbacc000,  0x10e59000,  0x125a1000,  0x12f00000,  0x14e7c000,  0x156de000,  0x192a1000,  0x1a2b9000,  0x1b4a0000,  0x1be9c000,  0x1d3bd000,  0x24242000,  0x2516b000,  0x2b88d000,  0x2b96a000,  0x2bcd3000,  0x2c5a9000,  0x2da74000,  0x2dba1000,  0x3097f000,  0x332ef000,  0x34525000,  0x36193000,  0x3725c000,  0x37e66000,  0x3d315000,  0x3e813000,  0x404ae000,  0x40c68000,  0x42f93000,  0x44b14000,  0x44b15000,  0x473b2000,  0x49048000,  0x4c794000,  0x50b60000,  0x52b3d000,  0x58c61000,  0x5b7d4000,  0x5ce71000,  0x5d21d000,  0x5d63e000,  0x5e00f000,  0x60e8b000,  0x66381000,  0x66c70000,  0x68430000,  0x707c2000,  0x71979000,  0x72681000,  0x74017000,  0x7721d000,  0x7a1be000,  0x7a2cd000,  0x7b225000,  0x7c311000,  0x7e03a000,  0x7e402000,  0x80000000,    },
  { 52,  62,  28,  47,  51,  37,  31,  36,  4,  58,  26,  29,  16,  59,  57,  33,  22,  27,  49,  44,  19,  56,  34,  23,  5,  14,  45,  48,  21,  25,  18,  12,  43,  53,  60,  17,  46,  15,  63,  30,  42,  38,  41,  8,  39,  20,  1,  10,  54,  40,  32,  24,  9,  2,  35,  3,  7,  0,  61,  11,  13,  55,  6,  50,    },
};
const pattern_t pat5 = {
  { 0xae7000,  0x436e000,  0x81e1000,  0xb276000,  0xf8bf000,  0xfb26000,  0xfe7e000,  0x137ad000,  0x14b8e000,  0x157aa000,  0x1981a000,  0x1a32f000,  0x1bc9e000,  0x1def5000,  0x1e8ef000,  0x2068f000,  0x22692000,  0x22a6c000,  0x255bf000,  0x26977000,  0x27619000,  0x2977c000,  0x2ce0c000,  0x2e1ec000,  0x2e26c000,  0x31ce8000,  0x34e6c000,  0x365cd000,  0x37e87000,  0x385e3000,  0x3a7e2000,  0x3a9c7000,  0x41597000,  0x42e8a000,  0x453cc000,  0x454bf000,  0x4b24c000,  0x4ba54000,  0x4e307000,  0x4f059000,  0x55d5a000,  0x56277000,  0x56b90000,  0x5882d000,  0x5a2c5000,  0x5b369000,  0x5d442000,  0x5d671000,  0x5fdd0000,  0x60ce0000,  0x63713000,  0x64130000,  0x65973000,  0x67ad9000,  0x68764000,  0x68bb2000,  0x690d1000,  0x6a2c8000,  0x73e9f000,  0x74e75000,  0x77861000,  0x77ee5000,  0x7cddb000,  0x80000000,    },
  { 42,  25,  15,  58,  32,  61,  30,  56,  48,  62,  38,  50,  7,  45,  16,  29,  12,  4,  41,  3,  27,  18,  57,  10,  51,  17,  21,  14,  35,  19,  44,  47,  49,  26,  59,  63,  28,  55,  20,  13,  5,  6,  37,  54,  40,  22,  23,  46,  11,  36,  34,  31,  2,  60,  9,  52,  24,  1,  53,  0,  39,  43,  8,  33,    },
};
const pattern_t pat6 = {
  { 0xad2000,  0x222f000,  0x64b4000,  0x6c66000,  0x6f35000,  0x9e50000,  0xe744000,  0xf129000,  0x101bb000,  0x11bf8000,  0x14b89000,  0x1691c000,  0x17a0d000,  0x1817a000,  0x1997a000,  0x1d736000,  0x1db33000,  0x1fdd8000,  0x21e56000,  0x2266c000,  0x22875000,  0x22b84000,  0x230ed000,  0x239c5000,  0x24e1a000,  0x275f5000,  0x29036000,  0x29f69000,  0x2e538000,  0x2efca000,  0x2f0bc000,  0x2f1bf000,  0x305cb000,  0x31ce7000,  0x345c4000,  0x35d4f000,  0x36e56000,  0x3ae9e000,  0x3cc27000,  0x40117000,  0x4299f000,  0x434c3000,  0x443d4000,  0x4552d000,  0x4a8a8000,  0x4cdea000,  0x51bd5000,  0x580c4000,  0x58381000,  0x59dc0000,  0x5ba7f000,  0x5d88b000,  0x5e0c4000,  0x5ee57000,  0x61f3f000,  0x63a4a000,  0x68a8a000,  0x68ec5000,  0x6937b000,  0x720be000,  0x72cf5000,  0x74fc8000,  0x76464000,  0x80000000,    },
  { 31,  46,  36,  22,  63,  12,  51,  60,  13,  44,  41,  6,  11,  17,  42,  24,  16,  61,  20,  26,  35,  21,  29,  55,  50,  45,  62,  19,  54,  9,  30,  34,  53,  52,  10,  39,  0,  49,  48,  38,  40,  28,  23,  56,  2,  5,  4,  59,  14,  57,  3,  25,  43,  32,  27,  47,  8,  7,  37,  33,  1,  18,  58,  15,    },
};
const pattern_t pat7 = {
  { 0xd83000,  0x1597000,  0x245b000,  0x6a75000,  0x8fda000,  0x960e000,  0xd310000,  0xe6cd000,  0x1409a000,  0x15221000,  0x16059000,  0x1b3a4000,  0x1ceea000,  0x1ed1a000,  0x1ef0f000,  0x21723000,  0x21efc000,  0x24594000,  0x26d7f000,  0x28c4f000,  0x2fa89000,  0x304f0000,  0x30dbb000,  0x30de3000,  0x3365d000,  0x36dbc000,  0x3acb2000,  0x3e291000,  0x3f7da000,  0x41352000,  0x41a0f000,  0x435c8000,  0x4475a000,  0x47536000,  0x47726000,  0x4a81f000,  0x4be4e000,  0x4bf05000,  0x4c15b000,  0x515b4000,  0x52ef5000,  0x548cc000,  0x5692a000,  0x59ef2000,  0x5b97c000,  0x5c4f0000,  0x5d1b9000,  0x618ed000,  0x61bcc000,  0x61e07000,  0x639a3000,  0x65302000,  0x68041000,  0x6be56000,  0x721a3000,  0x72c99000,  0x740b9000,  0x7586d000,  0x75eca000,  0x76406000,  0x7b68a000,  0x7dd26000,  0x7ed55000,  0x80000000,    },
  { 44,  57,  22,  35,  63,  11,  15,  49,  61,  40,  29,  20,  19,  42,  32,  12,  41,  6,  46,  60,  52,  5,  36,  10,  2,  8,  3,  33,  54,  39,  58,  48,  62,  7,  51,  34,  0,  1,  18,  9,  55,  31,  23,  38,  25,  21,  17,  24,  13,  50,  16,  14,  43,  53,  45,  28,  59,  37,  26,  30,  47,  27,  56,  4,    },
};
const pattern_t pat8 = {
  { 0x1b8000,  0x27eb000,  0x5a4d000,  0x6ecc000,  0xb52e000,  0xb70e000,  0xc6db000,  0xd83d000,  0xed51000,  0x13c59000,  0x13fef000,  0x142e1000,  0x192d0000,  0x1aa63000,  0x1e230000,  0x1f464000,  0x20de4000,  0x2234b000,  0x25459000,  0x27018000,  0x28263000,  0x29cc7000,  0x32227000,  0x32c63000,  0x34af0000,  0x37e27000,  0x3afc9000,  0x3c166000,  0x3df20000,  0x405bd000,  0x41273000,  0x45c39000,  0x471be000,  0x4758e000,  0x4b3fc000,  0x4c6b2000,  0x4c80f000,  0x4ccd6000,  0x4d9e0000,  0x4e07f000,  0x4eeda000,  0x541ae000,  0x58aa7000,  0x5a2c6000,  0x5a628000,  0x5ab94000,  0x5bddc000,  0x5d1d4000,  0x5e643000,  0x5f72f000,  0x64771000,  0x67bd4000,  0x6a28c000,  0x6c977000,  0x6cc4e000,  0x710c4000,  0x74b86000,  0x75cf7000,  0x77d4b000,  0x7870e000,  0x7c47c000,  0x7eb52000,  0x7fbea000,  0x80000000,    },
  { 7,  29,  62,  8,  54,  38,  35,  45,  60,  55,  1,  40,  4,  19,  50,  63,  48,  51,  13,  27,  33,  39,  52,  46,  10,  9,  56,  2,  42,  43,  47,  44,  17,  5,  25,  6,  57,  23,  15,  58,  59,  22,  14,  26,  32,  61,  30,  0,  11,  12,  36,  24,  53,  49,  3,  20,  31,  28,  34,  18,  41,  21,  16,  37,    },
};
const pattern_t pat9 = {
  { 0x5b59000,  0xa6d7000,  0xbad3000,  0xdf91000,  0x115ad000,  0x13fde000,  0x17618000,  0x1b8e9000,  0x1e1b7000,  0x1e97d000,  0x21737000,  0x21a5e000,  0x24140000,  0x2558f000,  0x2647a000,  0x28257000,  0x285f6000,  0x2cb7a000,  0x2ebb1000,  0x30ae8000,  0x31543000,  0x315cb000,  0x31616000,  0x335ba000,  0x33ed6000,  0x35cf3000,  0x4162b000,  0x4409b000,  0x4629a000,  0x4b745000,  0x4c0ba000,  0x4cbc5000,  0x4dd97000,  0x4f34b000,  0x4f637000,  0x539d6000,  0x53f3d000,  0x56383000,  0x5642b000,  0x5a71f000,  0x5affa000,  0x5b486000,  0x5b8ef000,  0x60d88000,  0x61629000,  0x625cd000,  0x63326000,  0x6735e000,  0x67379000,  0x6a26a000,  0x6a281000,  0x6b997000,  0x6c50d000,  0x6cc6c000,  0x6f496000,  0x717ad000,  0x732ec000,  0x744dc000,  0x771e8000,  0x77cf0000,  0x79cad000,  0x7bb21000,  0x7e7b4000,  0x80000000,    },
  { 35,  9,  46,  6,  29,  2,  3,  54,  55,  57,  41,  16,  44,  5,  0,  59,  10,  61,  22,  42,  47,  12,  14,  50,  39,  34,  21,  32,  25,  15,  26,  8,  38,  60,  28,  53,  62,  49,  58,  43,  36,  37,  52,  7,  19,  63,  17,  11,  45,  33,  23,  27,  24,  18,  48,  56,  31,  13,  51,  30,  4,  20,  40,  1,    },
};
const pattern_t pat10 = {
  { 0xa72000,  0x180a000,  0x6406000,  0x66df000,  0x83bb000,  0xa96f000,  0xd193000,  0x13b9b000,  0x13dae000,  0x16109000,  0x1853d000,  0x18887000,  0x19f0a000,  0x22151000,  0x229ba000,  0x26b58000,  0x2aaf4000,  0x2bf50000,  0x31a2e000,  0x31d4e000,  0x32196000,  0x3513a000,  0x36a2d000,  0x3746b000,  0x389ad000,  0x39d27000,  0x3dad3000,  0x3de55000,  0x3ea9b000,  0x3ec06000,  0x3f921000,  0x432d3000,  0x43bec000,  0x43dda000,  0x47b2b000,  0x4886e000,  0x4928e000,  0x49ad2000,  0x4d0df000,  0x4f40d000,  0x50959000,  0x54fa4000,  0x56091000,  0x5688d000,  0x5b7d8000,  0x5f6fd000,  0x601e4000,  0x64eaa000,  0x6752e000,  0x67fff000,  0x6a184000,  0x6ad7a000,  0x6adbc000,  0x6c434000,  0x6f451000,  0x6ffb4000,  0x707ee000,  0x71161000,  0x7146b000,  0x75dbf000,  0x77259000,  0x7acd4000,  0x7af71000,  0x80000000,    },
  { 61,  38,  5,  23,  62,  11,  53,  9,  17,  45,  30,  29,  41,  60,  39,  21,  40,  19,  44,  33,  42,  50,  56,  28,  32,  46,  43,  20,  16,  3,  54,  8,  4,  26,  15,  34,  47,  12,  6,  27,  48,  0,  1,  2,  57,  59,  7,  58,  49,  35,  24,  37,  52,  63,  10,  55,  36,  13,  14,  25,  18,  22,  31,  51,    },
};
const pattern_t pat11 = {
  { 0x996000,  0xaff000,  0x199a000,  0x46f3000,  0x74c0000,  0x758d000,  0xcd09000,  0xe48c000,  0xe8de000,  0xf111000,  0xf87b000,  0x10b1c000,  0x15d63000,  0x17b21000,  0x182d3000,  0x19167000,  0x198ce000,  0x1bd47000,  0x1dff1000,  0x1edc0000,  0x1f890000,  0x20860000,  0x23207000,  0x29bd5000,  0x2ac0f000,  0x2e395000,  0x2e707000,  0x329de000,  0x3497f000,  0x3807f000,  0x38a94000,  0x40a19000,  0x4168e000,  0x42ca0000,  0x42de9000,  0x45194000,  0x464f2000,  0x4700f000,  0x47dbb000,  0x4dae7000,  0x50660000,  0x535a8000,  0x5546b000,  0x57b55000,  0x5860a000,  0x5a9ee000,  0x5b8d9000,  0x5c49f000,  0x5cb4d000,  0x5d28c000,  0x60dcd000,  0x62557000,  0x64b0c000,  0x654cb000,  0x65746000,  0x65e29000,  0x6648f000,  0x66c56000,  0x6999e000,  0x6a11c000,  0x6ca04000,  0x79e60000,  0x7edce000,  0x80000000,    },
  { 16,  28,  2,  38,  10,  57,  21,  26,  61,  43,  46,  31,  56,  7,  47,  48,  58,  25,  63,  4,  59,  15,  32,  50,  1,  40,  53,  18,  17,  24,  29,  30,  55,  36,  49,  42,  41,  37,  23,  39,  6,  51,  33,  9,  45,  5,  35,  19,  44,  11,  34,  0,  27,  12,  60,  62,  20,  13,  22,  8,  14,  54,  3,  52,    },
};
const pattern_t pat12 = {
  { 0x513000,  0x1b72000,  0x1e27000,  0x3a63000,  0x1115c000,  0x158b4000,  0x1664f000,  0x1b667000,  0x1f838000,  0x21410000,  0x260c7000,  0x2cd8f000,  0x2ce37000,  0x2df16000,  0x2e59e000,  0x2e8eb000,  0x2ebd2000,  0x2f1d2000,  0x2fc42000,  0x30d00000,  0x31ef1000,  0x3301a000,  0x38097000,  0x38a1e000,  0x3d818000,  0x3e898000,  0x3f90f000,  0x47710000,  0x478bb000,  0x485ab000,  0x48e54000,  0x4cfe1000,  0x53a89000,  0x53d10000,  0x56308000,  0x56f3b000,  0x577f6000,  0x58734000,  0x5889b000,  0x58ad7000,  0x5923a000,  0x59aef000,  0x5dad3000,  0x5e32f000,  0x63b3a000,  0x665c9000,  0x68cde000,  0x69252000,  0x6a777000,  0x6a79a000,  0x6c1f0000,  0x6cb9a000,  0x6d319000,  0x6dc82000,  0x6dd4d000,  0x6e188000,  0x7184d000,  0x7206e000,  0x73980000,  0x740ad000,  0x75473000,  0x7614d000,  0x79b17000,  0x80000000,    },
  { 4,  60,  10,  35,  6,  31,  5,  18,  53,  17,  20,  8,  56,  29,  7,  48,  40,  0,  12,  39,  2,  43,  15,  61,  42,  30,  50,  14,  49,  38,  34,  58,  24,  55,  33,  63,  28,  51,  59,  46,  11,  22,  45,  41,  13,  44,  23,  47,  3,  32,  16,  54,  26,  19,  25,  52,  27,  57,  36,  9,  37,  21,  62,  1,    },
};
const pattern_t pat13 = {
  { 0x351e000,  0x5917000,  0xa992000,  0xc471000,  0xc69c000,  0xc6ed000,  0xc919000,  0xd713000,  0xec14000,  0xfa31000,  0x17567000,  0x1d81a000,  0x1f3c8000,  0x215b5000,  0x26e41000,  0x2a2d4000,  0x2b750000,  0x2bea0000,  0x2c5ae000,  0x2ca2c000,  0x30a94000,  0x31074000,  0x314d3000,  0x31b1e000,  0x31de2000,  0x32062000,  0x33da5000,  0x37838000,  0x385ec000,  0x38740000,  0x387f9000,  0x38be6000,  0x3d2f7000,  0x3eaf5000,  0x40266000,  0x402f3000,  0x40fda000,  0x4a4bd000,  0x4b831000,  0x4bfc9000,  0x4ccaa000,  0x4ea43000,  0x50190000,  0x547c8000,  0x58cc6000,  0x58ea5000,  0x59de1000,  0x5c7f1000,  0x5f713000,  0x63f9a000,  0x6686d000,  0x675c1000,  0x6cccc000,  0x6e409000,  0x6fb6d000,  0x71a70000,  0x72f60000,  0x77bd9000,  0x79013000,  0x7a8d3000,  0x7b341000,  0x7d8f7000,  0x7fe43000,  0x80000000,    },
  { 10,  52,  48,  8,  34,  4,  35,  19,  3,  17,  54,  45,  31,  38,  24,  44,  21,  36,  22,  11,  43,  40,  39,  26,  5,  30,  2,  7,  57,  12,  20,  32,  62,  15,  55,  14,  25,  58,  6,  33,  49,  9,  59,  27,  13,  63,  42,  61,  1,  51,  0,  50,  37,  47,  16,  18,  41,  56,  60,  46,  23,  28,  53,  29,    },
};
const pattern_t pat14 = {
  { 0xf8e000,  0x169a000,  0x3816000,  0x67a9000,  0x89f3000,  0xac97000,  0xc8da000,  0xf077000,  0x119f1000,  0x13902000,  0x19785000,  0x1ca7f000,  0x1f958000,  0x2027d000,  0x2251f000,  0x24661000,  0x25604000,  0x2b924000,  0x2be5f000,  0x2ec27000,  0x330a5000,  0x3349e000,  0x33a84000,  0x344fa000,  0x34514000,  0x37966000,  0x37f0b000,  0x37fcd000,  0x386d0000,  0x39600000,  0x39de4000,  0x3e601000,  0x3e7f1000,  0x42c61000,  0x48806000,  0x4d3d0000,  0x4f5ff000,  0x512c1000,  0x53fd4000,  0x59440000,  0x5b386000,  0x5e8a0000,  0x5fca3000,  0x6016c000,  0x61ca8000,  0x64915000,  0x66b99000,  0x67226000,  0x69b2f000,  0x6a473000,  0x6a590000,  0x6c844000,  0x6cb8c000,  0x713b5000,  0x7558a000,  0x75eab000,  0x76d15000,  0x77efe000,  0x78762000,  0x7bddc000,  0x7ce92000,  0x7dc44000,  0x7f54b000,  0x80000000,    },
  { 54,  31,  48,  10,  51,  49,  55,  19,  38,  18,  44,  5,  17,  20,  16,  11,  9,  3,  42,  59,  63,  45,  25,  60,  57,  21,  40,  29,  0,  39,  26,  7,  53,  12,  13,  2,  58,  41,  22,  8,  14,  28,  46,  24,  27,  6,  52,  32,  56,  4,  30,  36,  15,  47,  23,  37,  43,  35,  50,  33,  61,  34,  1,  62,    },
};
const pattern_t pat15 = {
  { 0xe16000,  0xec6000,  0xf6b000,  0x634b000,  0x6896000,  0x91db000,  0xc2c8000,  0xe083000,  0xfd7f000,  0x10479000,  0x17740000,  0x18292000,  0x1aaca000,  0x1cb55000,  0x1d2be000,  0x222af000,  0x2cb03000,  0x2fabc000,  0x32034000,  0x35c0f000,  0x3c5ec000,  0x40908000,  0x4128e000,  0x44411000,  0x44bcd000,  0x4f0ac000,  0x5167b000,  0x5541c000,  0x581bc000,  0x584e5000,  0x588fb000,  0x593d3000,  0x5b25d000,  0x5dc99000,  0x60b35000,  0x60ffc000,  0x638e8000,  0x63cf8000,  0x64ee1000,  0x6523c000,  0x654a1000,  0x687bf000,  0x68bef000,  0x69826000,  0x69d90000,  0x6a622000,  0x6d1b9000,  0x6d1e1000,  0x6d886000,  0x6fe4a000,  0x6feac000,  0x720b2000,  0x734dc000,  0x73530000,  0x73f1e000,  0x7479c000,  0x76e33000,  0x786dc000,  0x79b40000,  0x79e49000,  0x7b66c000,  0x7b904000,  0x7c906000,  0x80000000,    },
  { 6,  17,  62,  20,  61,  32,  22,  14,  28,  18,  3,  42,  63,  43,  46,  34,  29,  30,  35,  1,  37,  40,  10,  26,  5,  31,  15,  54,  8,  33,  9,  4,  39,  53,  23,  25,  41,  59,  12,  13,  60,  2,  7,  56,  58,  27,  11,  38,  36,  45,  47,  0,  57,  50,  48,  16,  51,  49,  55,  52,  44,  24,  19,  21,    },
};
const pattern_t pat16 = {
  { 0x596a000,  0x8644000,  0xa943000,  0xd59e000,  0x1062f000,  0x1082a000,  0x10c1b000,  0x10f9e000,  0x11e64000,  0x12e73000,  0x15ce7000,  0x16037000,  0x16d2e000,  0x17035000,  0x185ad000,  0x18d9b000,  0x19ac7000,  0x1b2fa000,  0x1cd6c000,  0x1d5f0000,  0x1f72c000,  0x20891000,  0x24bfa000,  0x25c1d000,  0x28e24000,  0x2a5f8000,  0x2e0ae000,  0x2fddf000,  0x3119d000,  0x332ee000,  0x3480a000,  0x34ea5000,  0x3534e000,  0x3538b000,  0x362e2000,  0x38f58000,  0x39ab0000,  0x3a519000,  0x3a62b000,  0x3b006000,  0x3d523000,  0x3e0f7000,  0x42366000,  0x42feb000,  0x44013000,  0x46b98000,  0x49794000,  0x4dce7000,  0x4f1f3000,  0x57ecd000,  0x5aaa2000,  0x5f419000,  0x61517000,  0x6797d000,  0x69a20000,  0x6a070000,  0x70575000,  0x75322000,  0x75a9e000,  0x79043000,  0x79875000,  0x7addc000,  0x7de88000,  0x80000000,    },
  { 26,  25,  6,  50,  32,  53,  34,  27,  3,  16,  49,  28,  46,  38,  56,  4,  18,  24,  51,  36,  63,  5,  48,  13,  43,  55,  0,  62,  35,  7,  41,  21,  44,  60,  31,  39,  14,  8,  61,  58,  52,  23,  59,  33,  10,  37,  20,  30,  40,  22,  11,  54,  57,  1,  29,  47,  2,  17,  19,  45,  15,  9,  12,  42,    },
};
const pattern_t pat17 = {
  { 0x28ab000,  0x3ac8000,  0x3fe1000,  0x63a7000,  0x90fc000,  0xb3f2000,  0xd2f2000,  0xe032000,  0x12d4c000,  0x13135000,  0x14652000,  0x15331000,  0x1570c000,  0x1688e000,  0x16bc3000,  0x1cbe3000,  0x1fe0f000,  0x2517f000,  0x26c6b000,  0x2a284000,  0x2a4e2000,  0x2add5000,  0x2bd06000,  0x2ca3a000,  0x2eb11000,  0x324d1000,  0x35662000,  0x38695000,  0x38ce7000,  0x391ac000,  0x398f9000,  0x39949000,  0x401f3000,  0x457f0000,  0x45c6d000,  0x4b561000,  0x522fc000,  0x54ef0000,  0x559f8000,  0x562a7000,  0x56a04000,  0x57b68000,  0x59702000,  0x5ffc9000,  0x63a76000,  0x63c37000,  0x65d3e000,  0x67130000,  0x6a03a000,  0x6bcd6000,  0x6be96000,  0x6bf52000,  0x6fcd9000,  0x7038c000,  0x70a47000,  0x72881000,  0x72ed0000,  0x75035000,  0x75c11000,  0x77fa5000,  0x797c9000,  0x79813000,  0x7bbbb000,  0x80000000,    },
  { 18,  15,  56,  5,  25,  47,  39,  55,  12,  14,  51,  33,  0,  7,  9,  44,  50,  31,  62,  59,  3,  35,  23,  17,  30,  60,  11,  24,  40,  20,  52,  2,  22,  8,  57,  42,  32,  54,  36,  48,  49,  13,  58,  10,  28,  63,  16,  41,  27,  21,  37,  4,  1,  29,  19,  6,  53,  45,  46,  38,  34,  43,  61,  26,    },
};
const pattern_t pat18 = {
  { 0x38d6000,  0x5379000,  0x5cae000,  0x5d20000,  0xa248000,  0xb4d0000,  0xd7c0000,  0xf731000,  0x116ae000,  0x151d2000,  0x1747d000,  0x1bfb6000,  0x1d758000,  0x2053d000,  0x24dda000,  0x25274000,  0x269c0000,  0x273e8000,  0x2a5d0000,  0x2ad34000,  0x3016b000,  0x30d1a000,  0x32960000,  0x34b3b000,  0x36e4f000,  0x37934000,  0x38c42000,  0x3c2d2000,  0x3d23d000,  0x3d89a000,  0x3dc85000,  0x3e9a7000,  0x3f25b000,  0x45bd1000,  0x48d94000,  0x4b126000,  0x4e17c000,  0x4f377000,  0x50908000,  0x51957000,  0x53410000,  0x5412c000,  0x55256000,  0x56b17000,  0x5707b000,  0x5bbe5000,  0x5d067000,  0x5e1c1000,  0x6380b000,  0x66009000,  0x68240000,  0x69fc4000,  0x6c327000,  0x6c5d2000,  0x6f69d000,  0x739c7000,  0x744bc000,  0x74cd8000,  0x787b8000,  0x78c61000,  0x7969d000,  0x79aae000,  0x7b032000,  0x80000000,    },
  { 16,  48,  50,  60,  13,  39,  20,  4,  63,  18,  14,  30,  55,  8,  62,  37,  43,  41,  11,  0,  36,  33,  34,  49,  17,  58,  38,  22,  19,  5,  21,  12,  47,  25,  57,  61,  7,  3,  10,  23,  52,  24,  6,  53,  2,  26,  1,  31,  28,  46,  42,  9,  45,  29,  27,  54,  32,  56,  51,  44,  35,  59,  40,  15,    },
};
const pattern_t pat19 = {
  { 0x297d000,  0x34e0000,  0x7801000,  0x9664000,  0x96fa000,  0xbb9f000,  0xc192000,  0xc4a5000,  0xca74000,  0xcce8000,  0x173d8000,  0x1a8d8000,  0x1b299000,  0x1b52d000,  0x1e813000,  0x2185e000,  0x21abe000,  0x2b9a4000,  0x2c4b6000,  0x2fa27000,  0x343ba000,  0x356fd000,  0x37c6e000,  0x38365000,  0x3a9e4000,  0x3b599000,  0x4296b000,  0x43196000,  0x4381e000,  0x44783000,  0x47a75000,  0x4bd78000,  0x4d05d000,  0x4edb2000,  0x4eefd000,  0x4fecc000,  0x51f68000,  0x5252b000,  0x5439e000,  0x55fb3000,  0x5814f000,  0x5939d000,  0x60a78000,  0x62a86000,  0x633b0000,  0x64a68000,  0x64b62000,  0x66207000,  0x66540000,  0x67f90000,  0x68bf3000,  0x6a069000,  0x6d2ac000,  0x70c9f000,  0x71bab000,  0x724bc000,  0x783d8000,  0x7900e000,  0x79399000,  0x79763000,  0x7c8a8000,  0x7e680000,  0x7f6de000,  0x80000000,    },
  { 14,  59,  60,  24,  18,  22,  62,  12,  45,  2,  32,  11,  25,  37,  13,  7,  50,  39,  56,  17,  47,  40,  29,  43,  15,  34,  4,  57,  31,  38,  21,  28,  36,  27,  42,  1,  23,  33,  5,  61,  44,  55,  8,  30,  10,  41,  19,  48,  16,  52,  49,  46,  54,  58,  6,  0,  51,  3,  26,  20,  53,  9,  35,  63,    },
};
const pattern_t pat20 = {
  { 0x8f7000,  0xa01000,  0x38e3000,  0x5299000,  0x6875000,  0x7f3e000,  0x827f000,  0x9413000,  0xca71000,  0xfb11000,  0x10beb000,  0x176be000,  0x1924f000,  0x1cfd6000,  0x1d20d000,  0x1ebb7000,  0x22c93000,  0x23601000,  0x2cf7a000,  0x2d3af000,  0x2e391000,  0x2f294000,  0x318ad000,  0x34ddd000,  0x365e4000,  0x3b8d2000,  0x3c0f8000,  0x3d2fd000,  0x3e431000,  0x3f0fe000,  0x4074e000,  0x40d1c000,  0x41936000,  0x4347b000,  0x452d7000,  0x486d3000,  0x4b47e000,  0x4b709000,  0x4c349000,  0x4ff13000,  0x50faa000,  0x51a07000,  0x52f30000,  0x55f29000,  0x57ad4000,  0x5909f000,  0x5a0f6000,  0x5de57000,  0x60d2f000,  0x625ff000,  0x6288e000,  0x65077000,  0x6a707000,  0x6a73f000,  0x6d720000,  0x6e390000,  0x6edc9000,  0x6ee78000,  0x77ac2000,  0x77ad3000,  0x7868f000,  0x79a1b000,  0x7aec6000,  0x80000000,    },
  { 21,  56,  38,  11,  62,  9,  30,  47,  34,  23,  37,  16,  5,  49,  10,  43,  4,  45,  36,  7,  42,  1,  53,  57,  20,  59,  55,  50,  46,  39,  60,  27,  12,  31,  48,  25,  15,  22,  44,  52,  14,  33,  0,  29,  17,  18,  2,  32,  24,  19,  6,  41,  54,  8,  35,  26,  61,  3,  51,  13,  63,  28,  40,  58,    },
};
const pattern_t pat21 = {
  { 0x2a8e000,  0xa4bd000,  0xa935000,  0xcc05000,  0xdfe4000,  0xe014000,  0xff46000,  0x18c8c000,  0x199ec000,  0x19ce0000,  0x1f684000,  0x1ff5c000,  0x22d58000,  0x27651000,  0x280e5000,  0x2e2a4000,  0x2e432000,  0x2f96e000,  0x2f9c3000,  0x3343d000,  0x338bb000,  0x34032000,  0x34101000,  0x368c2000,  0x37b95000,  0x39492000,  0x39932000,  0x3b611000,  0x3c89e000,  0x40aa9000,  0x42358000,  0x4890e000,  0x495c9000,  0x4a79d000,  0x4c58e000,  0x4df9a000,  0x4f304000,  0x4fa4c000,  0x54d1d000,  0x58461000,  0x58f43000,  0x5a3d1000,  0x5a765000,  0x5c5c0000,  0x60488000,  0x60fad000,  0x613e5000,  0x61d61000,  0x62d17000,  0x641ff000,  0x67f8b000,  0x69c5d000,  0x6b931000,  0x6efd4000,  0x70333000,  0x70857000,  0x721f6000,  0x72f53000,  0x74450000,  0x746f7000,  0x76067000,  0x7774a000,  0x77ea6000,  0x80000000,    },
  { 28,  51,  33,  2,  30,  55,  29,  17,  40,  48,  32,  9,  39,  1,  49,  50,  37,  43,  62,  11,  10,  26,  22,  6,  8,  7,  45,  47,  46,  42,  60,  5,  12,  56,  4,  23,  35,  25,  13,  16,  61,  54,  31,  63,  34,  19,  41,  59,  38,  24,  0,  58,  53,  44,  3,  18,  52,  20,  36,  27,  14,  21,  57,  15,    },
};
const pattern_t pat22 = {
  { 0x314d000,  0x4452000,  0x6673000,  0xab09000,  0xc80d000,  0x10eda000,  0x129c2000,  0x12f1f000,  0x13e9b000,  0x1450c000,  0x15aeb000,  0x1667c000,  0x190b2000,  0x19ac5000,  0x1c0ac000,  0x1c229000,  0x1ece8000,  0x1fc48000,  0x22abd000,  0x24268000,  0x2adce000,  0x2b809000,  0x30a11000,  0x31d08000,  0x36700000,  0x39e6a000,  0x3b84b000,  0x41e84000,  0x46301000,  0x4a326000,  0x50fda000,  0x5299a000,  0x56acf000,  0x57f66000,  0x586ab000,  0x58df5000,  0x591cc000,  0x59b91000,  0x59cbd000,  0x5b4d0000,  0x5cca7000,  0x5cfce000,  0x5d120000,  0x5d51a000,  0x5eaa0000,  0x5ebac000,  0x5f0e1000,  0x5f285000,  0x5f4d3000,  0x5ff61000,  0x60b51000,  0x61435000,  0x651fd000,  0x6b954000,  0x705aa000,  0x71a41000,  0x73ec7000,  0x75f92000,  0x76854000,  0x77cb9000,  0x782ca000,  0x7a2af000,  0x7eaa6000,  0x80000000,    },
  { 16,  8,  5,  59,  4,  18,  26,  43,  33,  57,  6,  47,  56,  46,  10,  54,  52,  0,  50,  30,  39,  24,  38,  63,  28,  25,  49,  31,  55,  62,  3,  17,  23,  13,  37,  53,  34,  14,  44,  12,  19,  36,  27,  61,  51,  42,  41,  60,  45,  1,  7,  35,  21,  58,  20,  15,  2,  9,  22,  29,  48,  32,  40,  11,    },
};
const pattern_t pat23 = {
  { 0x47000,  0x680000,  0x176a000,  0x1db8000,  0x600e000,  0x808c000,  0x9e58000,  0xa82f000,  0xaebb000,  0xc938000,  0xd0eb000,  0xdc5e000,  0xe503000,  0x11e56000,  0x12dbd000,  0x14681000,  0x15200000,  0x18256000,  0x1be75000,  0x1d2a0000,  0x1ed67000,  0x27e8a000,  0x2bc39000,  0x2bf4b000,  0x2c94f000,  0x2d575000,  0x2d82e000,  0x2e440000,  0x2ecda000,  0x2fbc2000,  0x33ab0000,  0x360b8000,  0x39630000,  0x3a654000,  0x3d2b6000,  0x3eeff000,  0x41590000,  0x417ea000,  0x42ff9000,  0x4bca4000,  0x503b0000,  0x508e4000,  0x52a2e000,  0x535b6000,  0x54335000,  0x57412000,  0x57dc6000,  0x590d9000,  0x5fc0a000,  0x60552000,  0x60665000,  0x6168d000,  0x65b16000,  0x67328000,  0x6742d000,  0x68c88000,  0x6b802000,  0x6f6d2000,  0x7040e000,  0x77e31000,  0x79c71000,  0x7da4a000,  0x7e26b000,  0x80000000,    },
  { 63,  50,  51,  33,  28,  35,  24,  14,  4,  23,  47,  11,  37,  41,  12,  55,  62,  32,  34,  30,  25,  43,  16,  0,  3,  49,  61,  15,  57,  46,  59,  44,  31,  27,  21,  53,  5,  2,  8,  56,  52,  22,  60,  40,  20,  1,  48,  18,  17,  19,  54,  29,  9,  38,  42,  6,  39,  45,  13,  10,  26,  58,  36,  7,    },
};
const pattern_t pat24 = {
  { 0x3890000,  0x3fd9000,  0x62d6000,  0x7df0000,  0x895c000,  0xab61000,  0xc23b000,  0x10ab3000,  0x1247c000,  0x13f00000,  0x16604000,  0x1a444000,  0x1c2c8000,  0x1c467000,  0x1d396000,  0x1e683000,  0x21080000,  0x2442a000,  0x27fea000,  0x282eb000,  0x28e2c000,  0x2a625000,  0x2b3b2000,  0x2bbd5000,  0x2c886000,  0x2cbe8000,  0x31518000,  0x35425000,  0x355f4000,  0x35d7a000,  0x3851d000,  0x396a6000,  0x3d10f000,  0x3d890000,  0x49238000,  0x4ab7e000,  0x4fadf000,  0x50603000,  0x5233a000,  0x53279000,  0x5586c000,  0x56968000,  0x58101000,  0x588b6000,  0x5bc19000,  0x5cc10000,  0x623f6000,  0x629f4000,  0x63176000,  0x63dcc000,  0x681d0000,  0x69c0e000,  0x6a9fa000,  0x6ae5e000,  0x6d2ba000,  0x6e422000,  0x73f94000,  0x77932000,  0x78b24000,  0x794c1000,  0x795d2000,  0x7ae08000,  0x7b3ce000,  0x80000000,    },
  { 56,  47,  54,  62,  29,  43,  25,  59,  41,  7,  52,  63,  15,  21,  16,  14,  39,  17,  45,  11,  27,  24,  55,  31,  53,  4,  6,  2,  20,  23,  5,  37,  32,  58,  13,  51,  1,  8,  3,  57,  46,  30,  35,  49,  18,  40,  9,  22,  42,  38,  34,  0,  19,  33,  26,  60,  10,  48,  36,  61,  44,  12,  50,  28,    },
};
const pattern_t pat25 = {
  { 0xcb000,  0x22bf000,  0x2461000,  0x246b000,  0x5c6f000,  0x5fb4000,  0x69a9000,  0x718c000,  0x92e6000,  0xbb2e000,  0xd916000,  0xf3dc000,  0xf568000,  0x10246000,  0x12d53000,  0x14dfd000,  0x1598a000,  0x1956a000,  0x1b01b000,  0x1b3b8000,  0x1ce06000,  0x20bc5000,  0x21351000,  0x233b0000,  0x23f2b000,  0x24e41000,  0x29cca000,  0x2b5bd000,  0x2ba68000,  0x2bf7f000,  0x31a58000,  0x34570000,  0x39941000,  0x3b765000,  0x3cd13000,  0x3d251000,  0x3fa05000,  0x40745000,  0x45c68000,  0x4a282000,  0x4ad19000,  0x4b4aa000,  0x4ca18000,  0x4e0b8000,  0x4eb97000,  0x4f68b000,  0x4fca2000,  0x52466000,  0x52edf000,  0x5602a000,  0x57f60000,  0x5cc18000,  0x5cee3000,  0x5da37000,  0x5dba4000,  0x64b77000,  0x66e9f000,  0x68b9d000,  0x6aac9000,  0x6d873000,  0x6f7e6000,  0x71036000,  0x75a54000,  0x80000000,    },
  { 1,  58,  13,  5,  62,  10,  49,  48,  19,  24,  54,  57,  20,  39,  35,  41,  28,  42,  6,  44,  34,  45,  55,  3,  2,  60,  38,  36,  30,  25,  7,  23,  53,  50,  61,  29,  40,  47,  22,  12,  27,  0,  52,  31,  8,  15,  37,  11,  46,  32,  4,  56,  17,  33,  26,  43,  51,  16,  9,  59,  63,  21,  14,  18,    },
};
const pattern_t pat26 = {
  { 0x1f4e000,  0x46f7000,  0x90a7000,  0xafe3000,  0xb2a8000,  0xb8b0000,  0xc480000,  0xc4e1000,  0xf03c000,  0xf075000,  0x14dbd000,  0x17728000,  0x1a146000,  0x1ab02000,  0x1af49000,  0x1be7a000,  0x1dc7a000,  0x1de5e000,  0x1f4f9000,  0x2092b000,  0x20a63000,  0x22937000,  0x22fe3000,  0x23e1c000,  0x28c46000,  0x294d6000,  0x2ad19000,  0x2b18b000,  0x2b233000,  0x2b685000,  0x2c792000,  0x2e6c2000,  0x2fa86000,  0x3320f000,  0x36f17000,  0x38406000,  0x38b1b000,  0x3a132000,  0x3b269000,  0x3cc43000,  0x3e2a2000,  0x3e3bb000,  0x3e83b000,  0x3ea14000,  0x4035d000,  0x4137f000,  0x4615b000,  0x50531000,  0x517c8000,  0x519e6000,  0x55ebc000,  0x594f8000,  0x5a732000,  0x5d2cb000,  0x5e409000,  0x5f394000,  0x5f3a8000,  0x60dc6000,  0x61373000,  0x6ebd6000,  0x6fd61000,  0x77161000,  0x7ce81000,  0x80000000,    },
  { 61,  48,  12,  55,  3,  58,  51,  56,  15,  29,  54,  11,  31,  49,  40,  37,  7,  4,  23,  35,  25,  18,  27,  43,  6,  41,  17,  45,  52,  53,  47,  16,  42,  0,  30,  13,  38,  62,  1,  8,  21,  28,  57,  9,  60,  19,  44,  50,  14,  36,  22,  2,  32,  59,  34,  10,  63,  39,  5,  24,  33,  20,  46,  26,    },
};
const pattern_t pat27 = {
  { 0xa6a000,  0x4c7a000,  0x5183000,  0x8dda000,  0x9cbd000,  0xb860000,  0x10c24000,  0x12dda000,  0x147ab000,  0x14aa4000,  0x16c8f000,  0x17d5b000,  0x18b5c000,  0x1a163000,  0x1b0a1000,  0x24221000,  0x25ef8000,  0x267f1000,  0x268b7000,  0x26b07000,  0x273ad000,  0x27bc2000,  0x2856c000,  0x29896000,  0x2efeb000,  0x331a7000,  0x348e8000,  0x3707f000,  0x3f444000,  0x3fe2a000,  0x433b3000,  0x435d3000,  0x46d82000,  0x4a9d3000,  0x4c6cf000,  0x4ca36000,  0x4ec42000,  0x4f79c000,  0x53cd3000,  0x58c78000,  0x5d910000,  0x616cc000,  0x62800000,  0x65ded000,  0x68831000,  0x6b321000,  0x6cd46000,  0x6d0fa000,  0x6d2f9000,  0x6e353000,  0x6fd5e000,  0x706c5000,  0x7249f000,  0x75d6c000,  0x77528000,  0x783ad000,  0x79738000,  0x79bfe000,  0x79ee9000,  0x7b74a000,  0x7bb41000,  0x7bbeb000,  0x7bbfb000,  0x80000000,    },
  { 61,  53,  12,  15,  26,  30,  32,  2,  16,  5,  39,  43,  20,  21,  49,  37,  11,  51,  18,  44,  31,  19,  24,  40,  1,  35,  50,  6,  57,  14,  46,  17,  22,  48,  29,  7,  34,  45,  10,  63,  23,  41,  54,  38,  4,  25,  42,  13,  56,  62,  36,  28,  33,  59,  55,  3,  9,  0,  58,  60,  47,  8,  52,  27,    },
};
const pattern_t pat28 = {
  { 0x439a000,  0x6860000,  0xd252000,  0x1105c000,  0x113c8000,  0x1429a000,  0x14922000,  0x15f32000,  0x1992f000,  0x1a1db000,  0x1a87c000,  0x1b260000,  0x1b292000,  0x1c253000,  0x1ea33000,  0x20bbc000,  0x215ae000,  0x25249000,  0x27c89000,  0x27e36000,  0x28bf2000,  0x29c27000,  0x2a575000,  0x2c6fa000,  0x31639000,  0x3184a000,  0x319c3000,  0x348a7000,  0x38aa8000,  0x39dd5000,  0x3a067000,  0x3c0dd000,  0x3cfd4000,  0x3ebb6000,  0x43259000,  0x46494000,  0x46fcb000,  0x4a050000,  0x4b5c4000,  0x4cff3000,  0x4edaa000,  0x4f025000,  0x542e1000,  0x55364000,  0x56338000,  0x56ef8000,  0x5711b000,  0x573d1000,  0x5943b000,  0x5b912000,  0x61ce2000,  0x65211000,  0x65dca000,  0x6dee2000,  0x6df30000,  0x7334d000,  0x73e76000,  0x7473a000,  0x75846000,  0x75fd0000,  0x77174000,  0x773e9000,  0x7a8db000,  0x80000000,    },
  { 43,  11,  8,  56,  5,  22,  42,  55,  14,  32,  2,  47,  24,  51,  35,  25,  15,  58,  41,  27,  33,  37,  4,  36,  7,  53,  26,  48,  38,  19,  29,  28,  40,  10,  1,  46,  59,  63,  61,  62,  60,  30,  21,  39,  44,  57,  20,  18,  17,  54,  49,  52,  3,  12,  45,  13,  50,  9,  16,  23,  0,  6,  31,  34,    },
};
const pattern_t pat29 = {
  { 0x363000,  0x9bc000,  0x1907000,  0x41d5000,  0x5a6e000,  0x9f36000,  0xa3ee000,  0x14b98000,  0x1845c000,  0x188ea000,  0x1b297000,  0x1c024000,  0x1e1eb000,  0x1f3a4000,  0x2047f000,  0x2420a000,  0x28871000,  0x296dd000,  0x2c92c000,  0x2dd42000,  0x3444f000,  0x35b90000,  0x3683c000,  0x3d8ea000,  0x3fe6b000,  0x4200e000,  0x421cf000,  0x42a46000,  0x44463000,  0x44e61000,  0x45c82000,  0x485f8000,  0x48fe8000,  0x4a532000,  0x4a6fd000,  0x4c8f9000,  0x4dbd7000,  0x5052a000,  0x512bb000,  0x5281d000,  0x5315d000,  0x5a202000,  0x5a9fc000,  0x5c11a000,  0x6010b000,  0x62aa3000,  0x63d05000,  0x6774c000,  0x6776d000,  0x68105000,  0x699d5000,  0x69bc2000,  0x6b1b9000,  0x704d5000,  0x73d5c000,  0x73d94000,  0x78483000,  0x78c8c000,  0x78cc5000,  0x7ac8d000,  0x7ae00000,  0x7b597000,  0x7e6ab000,  0x80000000,    },
  { 52,  40,  59,  29,  42,  34,  63,  44,  33,  37,  51,  23,  5,  36,  38,  43,  9,  4,  28,  55,  1,  6,  21,  26,  13,  24,  30,  15,  35,  17,  46,  20,  16,  10,  49,  48,  39,  62,  19,  14,  61,  27,  53,  2,  57,  58,  45,  7,  56,  50,  54,  25,  31,  11,  22,  47,  3,  0,  32,  12,  8,  41,  60,  18,    },
};
const pattern_t pat30 = {
  { 0x45c5000,  0x6bf3000,  0xc293000,  0xe470000,  0xe5b7000,  0x1256c000,  0x1444d000,  0x15699000,  0x16e86000,  0x1a4d5000,  0x1b803000,  0x1dcf9000,  0x1dd6f000,  0x1f57f000,  0x22879000,  0x263e9000,  0x29423000,  0x2a1a9000,  0x2a699000,  0x2c8fb000,  0x2d2e0000,  0x2ec5e000,  0x317a4000,  0x35a64000,  0x36967000,  0x37299000,  0x37c07000,  0x3b9bb000,  0x3c054000,  0x3ccbc000,  0x3d94a000,  0x3e2e9000,  0x3e7a4000,  0x40b98000,  0x44658000,  0x44738000,  0x44fe3000,  0x451d9000,  0x4536c000,  0x46df2000,  0x48855000,  0x503ce000,  0x53104000,  0x531fc000,  0x54c1b000,  0x56086000,  0x5642b000,  0x573a4000,  0x5887f000,  0x5a871000,  0x5c970000,  0x5e566000,  0x62b8f000,  0x642ce000,  0x65ee5000,  0x66db3000,  0x6727c000,  0x6a9a2000,  0x74a8f000,  0x7c29a000,  0x7cc57000,  0x7f221000,  0x7f28f000,  0x80000000,    },
  { 29,  35,  8,  49,  30,  55,  27,  38,  58,  61,  0,  28,  15,  39,  5,  37,  32,  42,  46,  54,  12,  14,  1,  31,  59,  11,  47,  9,  13,  50,  2,  62,  60,  18,  20,  51,  23,  24,  53,  6,  25,  48,  41,  3,  33,  57,  44,  19,  22,  52,  4,  45,  10,  21,  56,  36,  17,  43,  7,  63,  16,  34,  26,  40,    },
};
const pattern_t pat31 = {
  { 0x143f000,  0x2068000,  0x328c000,  0x70a6000,  0x92a7000,  0x93dd000,  0xa3a8000,  0xbe51000,  0xbfc8000,  0xe353000,  0x1272f000,  0x143a4000,  0x16825000,  0x20bf8000,  0x20d9f000,  0x21e32000,  0x22426000,  0x2246b000,  0x22cea000,  0x25dc2000,  0x29324000,  0x29cd1000,  0x2aa44000,  0x2cd84000,  0x2dafb000,  0x2e74b000,  0x2f5b1000,  0x3a7a9000,  0x3bb38000,  0x3c11a000,  0x3c30a000,  0x3e2f1000,  0x4187b000,  0x42190000,  0x44e34000,  0x4d850000,  0x53ceb000,  0x540db000,  0x54937000,  0x5530a000,  0x5a111000,  0x5c280000,  0x5ef17000,  0x5fccf000,  0x64434000,  0x6498e000,  0x662c4000,  0x6a7e2000,  0x6b5a1000,  0x6c11f000,  0x6dd97000,  0x6ef1b000,  0x6f44e000,  0x7084f000,  0x73b53000,  0x7872c000,  0x78ed7000,  0x7935b000,  0x79bf9000,  0x7a6af000,  0x7b6fd000,  0x7bd42000,  0x7f233000,  0x80000000,    },
  { 6,  25,  28,  44,  27,  43,  58,  33,  23,  21,  16,  48,  30,  26,  5,  20,  49,  38,  2,  45,  11,  61,  17,  0,  53,  13,  7,  52,  40,  31,  36,  4,  10,  8,  24,  22,  42,  63,  35,  60,  47,  29,  46,  19,  1,  3,  34,  55,  59,  14,  39,  12,  32,  50,  62,  54,  56,  51,  57,  15,  41,  18,  37,  9,    },
};
const pattern_t* patterns[] = {&trivial_pattern,
  &pat0, &pat1, &pat2, &pat3, &pat4, &pat5, &pat6, &pat7, 
  &pat8, &pat9, &pat10, &pat11, &pat12, &pat13, &pat14, &pat15,
  &pat16, &pat17, &pat18, &pat19, &pat20, &pat21, &pat22, &pat23, 
  &pat24, &pat25, &pat26, &pat27, &pat28, &pat29, &pat30, &pat31};

//static variables used by the worker threads
static int outfd = 0;
static sem_t chunk_sems[NUM_THREADS - 1][NUM_CHUNKS];

static void
usage()
{
  (void) fprintf(stderr, "usage: fsync_integrity <file name>\n");
  exit(2);
}


/* Fills a buffer with a special marker.  The marker contains information about
 * the file offset where this buffer is supposed to go, and whether it will
 * be written by a leader or a follower */
static void
marker_fill(uint64_t* buf, int file_ofs, size_t len, int thread_num){
  int ofs;
  uint32_t thread_mark = thread_num;
  uint32_t final_mark = 0xe005b0ca;  //"CABOOSE" in little endian
  for (ofs = file_ofs; ofs < file_ofs + len; ofs += sizeof(uint64_t)){
    uint64_t mark = ((thread_num == (NUM_THREADS - 1) ? 
          (uint64_t)final_mark : (uint64_t)thread_mark) << (uint64_t)32) |
      htonl(ofs & 0xFFFFFFFF);
    int buf_idx = (ofs - file_ofs) / sizeof(uint64_t);
    buf[buf_idx] = mark;
  }
}

static int
verify_file(int fd, const pattern_t* p_pat){
  int chunk_idx;
  int good_data = 1;
  int err = 0;

  for(chunk_idx=0; chunk_idx < NUM_CHUNKS; chunk_idx++){
    int i;
    uint32_t chunk_start, chunk_end;
    get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end);
    size_t size =  chunk_end - chunk_start;
    uint64_t* desired_buf = malloc(size);
    uint64_t* actual_buf = malloc(size);
    marker_fill(desired_buf, chunk_start, size, NUM_THREADS - 1);

    //read the actual data from the file
    if( read(fd, actual_buf, size) <= 0 ){
      perror("read");
      exit(1);
    }

    //verify the data
    for(i=0; i < size / sizeof(uint64_t); i++){
      int chunk_offset = sizeof(uint64_t) * i;
      int file_offset = chunk_start + chunk_offset;
      if (good_data && (actual_buf[i] != desired_buf[i])){
        fprintf(stderr, "fsync_integrity: miscompare at "
            "chunk %i, chunk offset %x, file offset %x\n",
            chunk_idx, chunk_offset, file_offset);
        fprintf(stderr, "Expected %016lx, got %016lx\n",
            desired_buf[i], actual_buf[i]);
        err = 1;
        good_data = 0;
      }
      else if (!good_data && (actual_buf[i] == desired_buf[i])) {
        fprintf(stderr, "fsync_integrity: miscompare ends at "
            "chunk %i, chunk offset %x, file offset %x\n",
            chunk_idx, chunk_offset, file_offset);
        good_data = 1;
      }
    }
    free(desired_buf);
    free(actual_buf);
  }

  return (err);
}

/* Writes a special marker to every byte within the chunk */
static void
write_chunk(const pattern_t* p_pat, int chunk_idx, int thread_num)
{
  uint32_t chunk_start, chunk_end;
  get_chunk_range(p_pat, chunk_idx, &chunk_start, &chunk_end);
  size_t size =  chunk_end - chunk_start;
  uint64_t* buf = malloc(size);
  marker_fill(buf, chunk_start, size, thread_num);
  pwrite(outfd, (void*)buf, size, chunk_start);
  free(buf);
}

static void
my_sync(int fd){
  if (fsync(fd)){
    perror("fsync");
    exit(1);
  }
}
  

static void*
worker(void* args)
{
  int perm_idx, thread_num;
  thread_data_t* data;

  data = (thread_data_t*)args;
  thread_num = data->thread_num;

  for(perm_idx = 0; perm_idx < NUM_CHUNKS; perm_idx++)
  {
    int chunk_idx = data->pat->permutation[perm_idx];
    /* Acquire the semaphore, if necessary */
    if (thread_num > 0) {
      if (-1 == sem_wait(&chunk_sems[thread_num - 1][chunk_idx])){
        perror("sem_wait");
        exit(1);
      }
    }
    /* Write the data */
    write_chunk(data->pat, chunk_idx, thread_num);
    /* Sync, if we are an even thread */
    if ((thread_num % 2) == 0)
      my_sync(outfd);
    /* Post the final semaphore, if necessary */
    if (thread_num < NUM_THREADS - 1) {
      if (sem_post(&chunk_sems[thread_num][chunk_idx]) == -1){
        perror("sem_post");
        exit(1);
      }
    }
  }
  return 0;
}


int
main(int argc, char** argv)
{
  int rep;
  int pat;
  pthread_t threads[NUM_THREADS];
  thread_data_t thread_data[NUM_THREADS];

  if (argc != 2){
    usage();
  }

  for(rep=0; rep < NUM_REPETITIONS; rep++){
    printf("Starting repetition %d\n", rep);
    for(pat=0; pat < sizeof(patterns) / sizeof(patterns[0]); pat++){
      int i;
      const pattern_t *pat_p = patterns[pat];
/*      pattern_t *pat_p = (void *)(uintptr_t)(const void *)patterns[pat];*/
      int sem_idx;
      int ofs=0;

/*        printf("Starting on patterns[%d]\n" , pat);*/
      outfd = open(argv[1], O_RDWR | O_CREAT | O_TRUNC, 0644);
      if (outfd == -1){
        perror("open");
        exit(1);
      }

      //set the file size
      if ( ftruncate(outfd, FSIZE)){
        perror("ftruncate");
        exit(1);
      }

      //Zero-fill the file to avoid fragmentation, as recommended by mmap(2).
      for(ofs=0; ofs < FSIZE; ofs+=CLUSTERSIZE){
        char buffer[CLUSTERSIZE];
        bzero(buffer, CLUSTERSIZE);
        if ( -1 == write(outfd, buffer, CLUSTERSIZE)){
          perror("write");
          exit(1);
        }
      }
      //Return the file pointer to the beginning prior to mmap
      if (-1 == lseek(outfd, 0, SEEK_SET)){
        perror("lseek");
      }

      //Create the semaphores
      for(i=0; i < NUM_THREADS - 1; i++) {
        for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){
          if (sem_init(&chunk_sems[i][sem_idx], 0, 0)){
            perror("sem_init");
            exit(1);
          }
        }
      }

      //Create the worker threads
      for(i=0; i < NUM_THREADS; i++) {
        thread_data[i].pat = pat_p;
        thread_data[i].thread_num = i;
        if (pthread_create(&threads[i], NULL, worker, (void*)&thread_data[i])){
          perror("pthread_create");
          exit(1);
        }
      }

      //Join the threads
      for(i=0; i < NUM_THREADS; i++) {
        if (pthread_join(threads[i], NULL)){
        perror("pthread_join");
        exit(1);
        }
      }

      //destroy the semaphores
      for(i=0; i < NUM_THREADS - 1; i++) {
        for(sem_idx=0; sem_idx < NUM_CHUNKS; sem_idx++){
          if (sem_destroy(&chunk_sems[i][sem_idx])){
            perror("sem_destory");
            exit(1);
          }
        }
      }
      //printf("destroyed semaphores\n");

      
      //Verify the contents of the file.
      if (verify_file(outfd, patterns[pat])) {
        exit(1);
      }
      //printf("finished verify_file\n");
      
      //close the file:
      if (close(outfd)){
        perror("close");
        exit(1);
      }
    }
  }
  
  return 0;
}