src/polynomial/elem/cl_UP_GF2.h

   1 // Univariate Polynomials over the ring GF(2) = Z/2Z.
   2
   3 #include "cln/GV_modinteger.h"
   4 #include "cln/modinteger.h"
   5 #include "cln/GV_integer.h"
   6 #include "cl_DS.h"
   7 #include "cln/abort.h"
   8
   9 namespace cln {
  10
  11 // This is actually defined in cl_GV_I.cc (*ugh*).
  12 struct cl_heap_GV_I_bits1 : public cl_heap_GV_I {
  13         uintD data[1];
  14 };
  15
  16 static cl_boolean gf2_equal (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
  17 {{
  18         DeclarePoly(cl_GV_MI,x);
  19         DeclarePoly(cl_GV_MI,y);
  20         unused UPR;
  21         var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
  22         var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
  23         var uintL xlen = xv->v.length();
  24         var uintL ylen = yv->v.length();
  25         if (!(xlen == ylen))
  26                 return cl_false;
  27         // We can compare full words since unused bits in the last word are 0.
  28         var uintL count = ceiling(xlen,intDsize);
  29         if (compare_loop_up(xv->data,yv->data,count) != 0)
  30                 return cl_false;
  31         return cl_true;
  32 }}
  33
  34 static const _cl_UP gf2_plus (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
  35 {{
  36         DeclarePoly(cl_GV_MI,x);
  37         DeclarePoly(cl_GV_MI,y);
  38         var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
  39         var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
  40         var uintL xlen = xv->v.length();
  41         var uintL ylen = yv->v.length();
  42         if (xlen == 0)
  43                 return _cl_UP(UPR, y);
  44         if (ylen == 0)
  45                 return _cl_UP(UPR, x);
  46         // Now xlen > 0, ylen > 0.
  47         var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
  48         if (xlen > ylen) {
  49                 var cl_GV_MI result = cl_GV_MI(xlen,R);
  50                 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
  51                 // Copy xv into rv.
  52                 copy_loop_up(xv->data,rv->data,ceiling(xlen,intDsize));
  53                 // Add yv to rv.
  54                 xor_loop_up(rv->data,yv->data,ceiling(ylen,intDsize));
  55                 return _cl_UP(UPR, result);
  56         }
  57         if (xlen < ylen) {
  58                 var cl_GV_MI result = cl_GV_MI(ylen,R);
  59                 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
  60                 // Copy yv into rv.
  61                 copy_loop_up(yv->data,rv->data,ceiling(ylen,intDsize));
  62                 // Add xv to rv.
  63                 xor_loop_up(rv->data,xv->data,ceiling(xlen,intDsize));
  64                 return _cl_UP(UPR, result);
  65         }
  66         // Now xlen = ylen > 0. Add and normalize simultaneously.
  67         for (;;) {
  68                 var uintL index = floor(xlen-1,intDsize);
  69                 var uintD rword = xv->data[index] ^ yv->data[index];
  70                 if (rword == 0) {
  71                         xlen = index*intDsize;
  72                         if (xlen == 0)
  73                                 return _cl_UP(UPR, cl_null_GV_I);
  74                 } else {
  75                         xlen = index*intDsize;
  76                         integerlengthD(rword, xlen += );
  77                         // Build result.
  78                         var cl_GV_MI result = cl_GV_MI(xlen,R);
  79                         var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
  80                         copy_loop_up(xv->data,rv->data,index);
  81                         xor_loop_up(rv->data,yv->data,index);
  82                         rv->data[index] = rword;
  83                         return _cl_UP(UPR, result);
  84                 }
  85         }
  86 }}
  87
  88 // In characteristic 2, x-y = x+y.
  89 #define gf2_minus  gf2_plus
  90
  91 // In characteristic 2, -x = x.
  92 static const _cl_UP gf2_uminus (cl_heap_univpoly_ring* UPR, const _cl_UP& x)
  93 {
  94         unused UPR;
  95         return x;
  96 }
  97
  98 #if !(defined(__sparc__) || defined(__sparc64__))
  99 // Multiplication of polynomials over GF(2) can unfortunately not profit
 100 // from hardware multiply instructions. Use a table instead.
 101 // This is a 2^8 x 2^4 table. Maybe a 2^6 x 2^6 table would be better?
 102 // (LiDIA uses a 2^8 x 2^8 table, which is way too large.)
 103 static uint16 gf2_mul_table[0x100][0x10] =
 104   {
 105     { 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
 106       0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000 },
 107     { 0x000, 0x001, 0x002, 0x003, 0x004, 0x005, 0x006, 0x007,
 108       0x008, 0x009, 0x00A, 0x00B, 0x00C, 0x00D, 0x00E, 0x00F },
 109     { 0x000, 0x002, 0x004, 0x006, 0x008, 0x00A, 0x00C, 0x00E,
 110       0x010, 0x012, 0x014, 0x016, 0x018, 0x01A, 0x01C, 0x01E },
 111     { 0x000, 0x003, 0x006, 0x005, 0x00C, 0x00F, 0x00A, 0x009,
 112       0x018, 0x01B, 0x01E, 0x01D, 0x014, 0x017, 0x012, 0x011 },
 113     { 0x000, 0x004, 0x008, 0x00C, 0x010, 0x014, 0x018, 0x01C,
 114       0x020, 0x024, 0x028, 0x02C, 0x030, 0x034, 0x038, 0x03C },
 115     { 0x000, 0x005, 0x00A, 0x00F, 0x014, 0x011, 0x01E, 0x01B,
 116       0x028, 0x02D, 0x022, 0x027, 0x03C, 0x039, 0x036, 0x033 },
 117     { 0x000, 0x006, 0x00C, 0x00A, 0x018, 0x01E, 0x014, 0x012,
 118       0x030, 0x036, 0x03C, 0x03A, 0x028, 0x02E, 0x024, 0x022 },
 119     { 0x000, 0x007, 0x00E, 0x009, 0x01C, 0x01B, 0x012, 0x015,
 120       0x038, 0x03F, 0x036, 0x031, 0x024, 0x023, 0x02A, 0x02D },
 121     { 0x000, 0x008, 0x010, 0x018, 0x020, 0x028, 0x030, 0x038,
 122       0x040, 0x048, 0x050, 0x058, 0x060, 0x068, 0x070, 0x078 },
 123     { 0x000, 0x009, 0x012, 0x01B, 0x024, 0x02D, 0x036, 0x03F,
 124       0x048, 0x041, 0x05A, 0x053, 0x06C, 0x065, 0x07E, 0x077 },
 125     { 0x000, 0x00A, 0x014, 0x01E, 0x028, 0x022, 0x03C, 0x036,
 126       0x050, 0x05A, 0x044, 0x04E, 0x078, 0x072, 0x06C, 0x066 },
 127     { 0x000, 0x00B, 0x016, 0x01D, 0x02C, 0x027, 0x03A, 0x031,
 128       0x058, 0x053, 0x04E, 0x045, 0x074, 0x07F, 0x062, 0x069 },
 129     { 0x000, 0x00C, 0x018, 0x014, 0x030, 0x03C, 0x028, 0x024,
 130       0x060, 0x06C, 0x078, 0x074, 0x050, 0x05C, 0x048, 0x044 },
 131     { 0x000, 0x00D, 0x01A, 0x017, 0x034, 0x039, 0x02E, 0x023,
 132       0x068, 0x065, 0x072, 0x07F, 0x05C, 0x051, 0x046, 0x04B },
 133     { 0x000, 0x00E, 0x01C, 0x012, 0x038, 0x036, 0x024, 0x02A,
 134       0x070, 0x07E, 0x06C, 0x062, 0x048, 0x046, 0x054, 0x05A },
 135     { 0x000, 0x00F, 0x01E, 0x011, 0x03C, 0x033, 0x022, 0x02D,
 136       0x078, 0x077, 0x066, 0x069, 0x044, 0x04B, 0x05A, 0x055 },
 137     { 0x000, 0x010, 0x020, 0x030, 0x040, 0x050, 0x060, 0x070,
 138       0x080, 0x090, 0x0A0, 0x0B0, 0x0C0, 0x0D0, 0x0E0, 0x0F0 },
 139     { 0x000, 0x011, 0x022, 0x033, 0x044, 0x055, 0x066, 0x077,
 140       0x088, 0x099, 0x0AA, 0x0BB, 0x0CC, 0x0DD, 0x0EE, 0x0FF },
 141     { 0x000, 0x012, 0x024, 0x036, 0x048, 0x05A, 0x06C, 0x07E,
 142       0x090, 0x082, 0x0B4, 0x0A6, 0x0D8, 0x0CA, 0x0FC, 0x0EE },
 143     { 0x000, 0x013, 0x026, 0x035, 0x04C, 0x05F, 0x06A, 0x079,
 144       0x098, 0x08B, 0x0BE, 0x0AD, 0x0D4, 0x0C7, 0x0F2, 0x0E1 },
 145     { 0x000, 0x014, 0x028, 0x03C, 0x050, 0x044, 0x078, 0x06C,
 146       0x0A0, 0x0B4, 0x088, 0x09C, 0x0F0, 0x0E4, 0x0D8, 0x0CC },
 147     { 0x000, 0x015, 0x02A, 0x03F, 0x054, 0x041, 0x07E, 0x06B,
 148       0x0A8, 0x0BD, 0x082, 0x097, 0x0FC, 0x0E9, 0x0D6, 0x0C3 },
 149     { 0x000, 0x016, 0x02C, 0x03A, 0x058, 0x04E, 0x074, 0x062,
 150       0x0B0, 0x0A6, 0x09C, 0x08A, 0x0E8, 0x0FE, 0x0C4, 0x0D2 },
 151     { 0x000, 0x017, 0x02E, 0x039, 0x05C, 0x04B, 0x072, 0x065,
 152       0x0B8, 0x0AF, 0x096, 0x081, 0x0E4, 0x0F3, 0x0CA, 0x0DD },
 153     { 0x000, 0x018, 0x030, 0x028, 0x060, 0x078, 0x050, 0x048,
 154       0x0C0, 0x0D8, 0x0F0, 0x0E8, 0x0A0, 0x0B8, 0x090, 0x088 },
 155     { 0x000, 0x019, 0x032, 0x02B, 0x064, 0x07D, 0x056, 0x04F,
 156       0x0C8, 0x0D1, 0x0FA, 0x0E3, 0x0AC, 0x0B5, 0x09E, 0x087 },
 157     { 0x000, 0x01A, 0x034, 0x02E, 0x068, 0x072, 0x05C, 0x046,
 158       0x0D0, 0x0CA, 0x0E4, 0x0FE, 0x0B8, 0x0A2, 0x08C, 0x096 },
 159     { 0x000, 0x01B, 0x036, 0x02D, 0x06C, 0x077, 0x05A, 0x041,
 160       0x0D8, 0x0C3, 0x0EE, 0x0F5, 0x0B4, 0x0AF, 0x082, 0x099 },
 161     { 0x000, 0x01C, 0x038, 0x024, 0x070, 0x06C, 0x048, 0x054,
 162       0x0E0, 0x0FC, 0x0D8, 0x0C4, 0x090, 0x08C, 0x0A8, 0x0B4 },
 163     { 0x000, 0x01D, 0x03A, 0x027, 0x074, 0x069, 0x04E, 0x053,
 164       0x0E8, 0x0F5, 0x0D2, 0x0CF, 0x09C, 0x081, 0x0A6, 0x0BB },
 165     { 0x000, 0x01E, 0x03C, 0x022, 0x078, 0x066, 0x044, 0x05A,
 166       0x0F0, 0x0EE, 0x0CC, 0x0D2, 0x088, 0x096, 0x0B4, 0x0AA },
 167     { 0x000, 0x01F, 0x03E, 0x021, 0x07C, 0x063, 0x042, 0x05D,
 168       0x0F8, 0x0E7, 0x0C6, 0x0D9, 0x084, 0x09B, 0x0BA, 0x0A5 },
 169     { 0x000, 0x020, 0x040, 0x060, 0x080, 0x0A0, 0x0C0, 0x0E0,
 170       0x100, 0x120, 0x140, 0x160, 0x180, 0x1A0, 0x1C0, 0x1E0 },
 171     { 0x000, 0x021, 0x042, 0x063, 0x084, 0x0A5, 0x0C6, 0x0E7,
 172       0x108, 0x129, 0x14A, 0x16B, 0x18C, 0x1AD, 0x1CE, 0x1EF },
 173     { 0x000, 0x022, 0x044, 0x066, 0x088, 0x0AA, 0x0CC, 0x0EE,
 174       0x110, 0x132, 0x154, 0x176, 0x198, 0x1BA, 0x1DC, 0x1FE },
 175     { 0x000, 0x023, 0x046, 0x065, 0x08C, 0x0AF, 0x0CA, 0x0E9,
 176       0x118, 0x13B, 0x15E, 0x17D, 0x194, 0x1B7, 0x1D2, 0x1F1 },
 177     { 0x000, 0x024, 0x048, 0x06C, 0x090, 0x0B4, 0x0D8, 0x0FC,
 178       0x120, 0x104, 0x168, 0x14C, 0x1B0, 0x194, 0x1F8, 0x1DC },
 179     { 0x000, 0x025, 0x04A, 0x06F, 0x094, 0x0B1, 0x0DE, 0x0FB,
 180       0x128, 0x10D, 0x162, 0x147, 0x1BC, 0x199, 0x1F6, 0x1D3 },
 181     { 0x000, 0x026, 0x04C, 0x06A, 0x098, 0x0BE, 0x0D4, 0x0F2,
 182       0x130, 0x116, 0x17C, 0x15A, 0x1A8, 0x18E, 0x1E4, 0x1C2 },
 183     { 0x000, 0x027, 0x04E, 0x069, 0x09C, 0x0BB, 0x0D2, 0x0F5,
 184       0x138, 0x11F, 0x176, 0x151, 0x1A4, 0x183, 0x1EA, 0x1CD },
 185     { 0x000, 0x028, 0x050, 0x078, 0x0A0, 0x088, 0x0F0, 0x0D8,
 186       0x140, 0x168, 0x110, 0x138, 0x1E0, 0x1C8, 0x1B0, 0x198 },
 187     { 0x000, 0x029, 0x052, 0x07B, 0x0A4, 0x08D, 0x0F6, 0x0DF,
 188       0x148, 0x161, 0x11A, 0x133, 0x1EC, 0x1C5, 0x1BE, 0x197 },
 189     { 0x000, 0x02A, 0x054, 0x07E, 0x0A8, 0x082, 0x0FC, 0x0D6,
 190       0x150, 0x17A, 0x104, 0x12E, 0x1F8, 0x1D2, 0x1AC, 0x186 },
 191     { 0x000, 0x02B, 0x056, 0x07D, 0x0AC, 0x087, 0x0FA, 0x0D1,
 192       0x158, 0x173, 0x10E, 0x125, 0x1F4, 0x1DF, 0x1A2, 0x189 },
 193     { 0x000, 0x02C, 0x058, 0x074, 0x0B0, 0x09C, 0x0E8, 0x0C4,
 194       0x160, 0x14C, 0x138, 0x114, 0x1D0, 0x1FC, 0x188, 0x1A4 },
 195     { 0x000, 0x02D, 0x05A, 0x077, 0x0B4, 0x099, 0x0EE, 0x0C3,
 196       0x168, 0x145, 0x132, 0x11F, 0x1DC, 0x1F1, 0x186, 0x1AB },
 197     { 0x000, 0x02E, 0x05C, 0x072, 0x0B8, 0x096, 0x0E4, 0x0CA,
 198       0x170, 0x15E, 0x12C, 0x102, 0x1C8, 0x1E6, 0x194, 0x1BA },
 199     { 0x000, 0x02F, 0x05E, 0x071, 0x0BC, 0x093, 0x0E2, 0x0CD,
 200       0x178, 0x157, 0x126, 0x109, 0x1C4, 0x1EB, 0x19A, 0x1B5 },
 201     { 0x000, 0x030, 0x060, 0x050, 0x0C0, 0x0F0, 0x0A0, 0x090,
 202       0x180, 0x1B0, 0x1E0, 0x1D0, 0x140, 0x170, 0x120, 0x110 },
 203     { 0x000, 0x031, 0x062, 0x053, 0x0C4, 0x0F5, 0x0A6, 0x097,
 204       0x188, 0x1B9, 0x1EA, 0x1DB, 0x14C, 0x17D, 0x12E, 0x11F },
 205     { 0x000, 0x032, 0x064, 0x056, 0x0C8, 0x0FA, 0x0AC, 0x09E,
 206       0x190, 0x1A2, 0x1F4, 0x1C6, 0x158, 0x16A, 0x13C, 0x10E },
 207     { 0x000, 0x033, 0x066, 0x055, 0x0CC, 0x0FF, 0x0AA, 0x099,
 208       0x198, 0x1AB, 0x1FE, 0x1CD, 0x154, 0x167, 0x132, 0x101 },
 209     { 0x000, 0x034, 0x068, 0x05C, 0x0D0, 0x0E4, 0x0B8, 0x08C,
 210       0x1A0, 0x194, 0x1C8, 0x1FC, 0x170, 0x144, 0x118, 0x12C },
 211     { 0x000, 0x035, 0x06A, 0x05F, 0x0D4, 0x0E1, 0x0BE, 0x08B,
 212       0x1A8, 0x19D, 0x1C2, 0x1F7, 0x17C, 0x149, 0x116, 0x123 },
 213     { 0x000, 0x036, 0x06C, 0x05A, 0x0D8, 0x0EE, 0x0B4, 0x082,
 214       0x1B0, 0x186, 0x1DC, 0x1EA, 0x168, 0x15E, 0x104, 0x132 },
 215     { 0x000, 0x037, 0x06E, 0x059, 0x0DC, 0x0EB, 0x0B2, 0x085,
 216       0x1B8, 0x18F, 0x1D6, 0x1E1, 0x164, 0x153, 0x10A, 0x13D },
 217     { 0x000, 0x038, 0x070, 0x048, 0x0E0, 0x0D8, 0x090, 0x0A8,
 218       0x1C0, 0x1F8, 0x1B0, 0x188, 0x120, 0x118, 0x150, 0x168 },
 219     { 0x000, 0x039, 0x072, 0x04B, 0x0E4, 0x0DD, 0x096, 0x0AF,
 220       0x1C8, 0x1F1, 0x1BA, 0x183, 0x12C, 0x115, 0x15E, 0x167 },
 221     { 0x000, 0x03A, 0x074, 0x04E, 0x0E8, 0x0D2, 0x09C, 0x0A6,
 222       0x1D0, 0x1EA, 0x1A4, 0x19E, 0x138, 0x102, 0x14C, 0x176 },
 223     { 0x000, 0x03B, 0x076, 0x04D, 0x0EC, 0x0D7, 0x09A, 0x0A1,
 224       0x1D8, 0x1E3, 0x1AE, 0x195, 0x134, 0x10F, 0x142, 0x179 },
 225     { 0x000, 0x03C, 0x078, 0x044, 0x0F0, 0x0CC, 0x088, 0x0B4,
 226       0x1E0, 0x1DC, 0x198, 0x1A4, 0x110, 0x12C, 0x168, 0x154 },
 227     { 0x000, 0x03D, 0x07A, 0x047, 0x0F4, 0x0C9, 0x08E, 0x0B3,
 228       0x1E8, 0x1D5, 0x192, 0x1AF, 0x11C, 0x121, 0x166, 0x15B },
 229     { 0x000, 0x03E, 0x07C, 0x042, 0x0F8, 0x0C6, 0x084, 0x0BA,
 230       0x1F0, 0x1CE, 0x18C, 0x1B2, 0x108, 0x136, 0x174, 0x14A },
 231     { 0x000, 0x03F, 0x07E, 0x041, 0x0FC, 0x0C3, 0x082, 0x0BD,
 232       0x1F8, 0x1C7, 0x186, 0x1B9, 0x104, 0x13B, 0x17A, 0x145 },
 233     { 0x000, 0x040, 0x080, 0x0C0, 0x100, 0x140, 0x180, 0x1C0,
 234       0x200, 0x240, 0x280, 0x2C0, 0x300, 0x340, 0x380, 0x3C0 },
 235     { 0x000, 0x041, 0x082, 0x0C3, 0x104, 0x145, 0x186, 0x1C7,
 236       0x208, 0x249, 0x28A, 0x2CB, 0x30C, 0x34D, 0x38E, 0x3CF },
 237     { 0x000, 0x042, 0x084, 0x0C6, 0x108, 0x14A, 0x18C, 0x1CE,
 238       0x210, 0x252, 0x294, 0x2D6, 0x318, 0x35A, 0x39C, 0x3DE },
 239     { 0x000, 0x043, 0x086, 0x0C5, 0x10C, 0x14F, 0x18A, 0x1C9,
 240       0x218, 0x25B, 0x29E, 0x2DD, 0x314, 0x357, 0x392, 0x3D1 },
 241     { 0x000, 0x044, 0x088, 0x0CC, 0x110, 0x154, 0x198, 0x1DC,
 242       0x220, 0x264, 0x2A8, 0x2EC, 0x330, 0x374, 0x3B8, 0x3FC },
 243     { 0x000, 0x045, 0x08A, 0x0CF, 0x114, 0x151, 0x19E, 0x1DB,
 244       0x228, 0x26D, 0x2A2, 0x2E7, 0x33C, 0x379, 0x3B6, 0x3F3 },
 245     { 0x000, 0x046, 0x08C, 0x0CA, 0x118, 0x15E, 0x194, 0x1D2,
 246       0x230, 0x276, 0x2BC, 0x2FA, 0x328, 0x36E, 0x3A4, 0x3E2 },
 247     { 0x000, 0x047, 0x08E, 0x0C9, 0x11C, 0x15B, 0x192, 0x1D5,
 248       0x238, 0x27F, 0x2B6, 0x2F1, 0x324, 0x363, 0x3AA, 0x3ED },
 249     { 0x000, 0x048, 0x090, 0x0D8, 0x120, 0x168, 0x1B0, 0x1F8,
 250       0x240, 0x208, 0x2D0, 0x298, 0x360, 0x328, 0x3F0, 0x3B8 },
 251     { 0x000, 0x049, 0x092, 0x0DB, 0x124, 0x16D, 0x1B6, 0x1FF,
 252       0x248, 0x201, 0x2DA, 0x293, 0x36C, 0x325, 0x3FE, 0x3B7 },
 253     { 0x000, 0x04A, 0x094, 0x0DE, 0x128, 0x162, 0x1BC, 0x1F6,
 254       0x250, 0x21A, 0x2C4, 0x28E, 0x378, 0x332, 0x3EC, 0x3A6 },
 255     { 0x000, 0x04B, 0x096, 0x0DD, 0x12C, 0x167, 0x1BA, 0x1F1,
 256       0x258, 0x213, 0x2CE, 0x285, 0x374, 0x33F, 0x3E2, 0x3A9 },
 257     { 0x000, 0x04C, 0x098, 0x0D4, 0x130, 0x17C, 0x1A8, 0x1E4,
 258       0x260, 0x22C, 0x2F8, 0x2B4, 0x350, 0x31C, 0x3C8, 0x384 },
 259     { 0x000, 0x04D, 0x09A, 0x0D7, 0x134, 0x179, 0x1AE, 0x1E3,
 260       0x268, 0x225, 0x2F2, 0x2BF, 0x35C, 0x311, 0x3C6, 0x38B },
 261     { 0x000, 0x04E, 0x09C, 0x0D2, 0x138, 0x176, 0x1A4, 0x1EA,
 262       0x270, 0x23E, 0x2EC, 0x2A2, 0x348, 0x306, 0x3D4, 0x39A },
 263     { 0x000, 0x04F, 0x09E, 0x0D1, 0x13C, 0x173, 0x1A2, 0x1ED,
 264       0x278, 0x237, 0x2E6, 0x2A9, 0x344, 0x30B, 0x3DA, 0x395 },
 265     { 0x000, 0x050, 0x0A0, 0x0F0, 0x140, 0x110, 0x1E0, 0x1B0,
 266       0x280, 0x2D0, 0x220, 0x270, 0x3C0, 0x390, 0x360, 0x330 },
 267     { 0x000, 0x051, 0x0A2, 0x0F3, 0x144, 0x115, 0x1E6, 0x1B7,
 268       0x288, 0x2D9, 0x22A, 0x27B, 0x3CC, 0x39D, 0x36E, 0x33F },
 269     { 0x000, 0x052, 0x0A4, 0x0F6, 0x148, 0x11A, 0x1EC, 0x1BE,
 270       0x290, 0x2C2, 0x234, 0x266, 0x3D8, 0x38A, 0x37C, 0x32E },
 271     { 0x000, 0x053, 0x0A6, 0x0F5, 0x14C, 0x11F, 0x1EA, 0x1B9,
 272       0x298, 0x2CB, 0x23E, 0x26D, 0x3D4, 0x387, 0x372, 0x321 },
 273     { 0x000, 0x054, 0x0A8, 0x0FC, 0x150, 0x104, 0x1F8, 0x1AC,
 274       0x2A0, 0x2F4, 0x208, 0x25C, 0x3F0, 0x3A4, 0x358, 0x30C },
 275     { 0x000, 0x055, 0x0AA, 0x0FF, 0x154, 0x101, 0x1FE, 0x1AB,
 276       0x2A8, 0x2FD, 0x202, 0x257, 0x3FC, 0x3A9, 0x356, 0x303 },
 277     { 0x000, 0x056, 0x0AC, 0x0FA, 0x158, 0x10E, 0x1F4, 0x1A2,
 278       0x2B0, 0x2E6, 0x21C, 0x24A, 0x3E8, 0x3BE, 0x344, 0x312 },
 279     { 0x000, 0x057, 0x0AE, 0x0F9, 0x15C, 0x10B, 0x1F2, 0x1A5,
 280       0x2B8, 0x2EF, 0x216, 0x241, 0x3E4, 0x3B3, 0x34A, 0x31D },
 281     { 0x000, 0x058, 0x0B0, 0x0E8, 0x160, 0x138, 0x1D0, 0x188,
 282       0x2C0, 0x298, 0x270, 0x228, 0x3A0, 0x3F8, 0x310, 0x348 },
 283     { 0x000, 0x059, 0x0B2, 0x0EB, 0x164, 0x13D, 0x1D6, 0x18F,
 284       0x2C8, 0x291, 0x27A, 0x223, 0x3AC, 0x3F5, 0x31E, 0x347 },
 285     { 0x000, 0x05A, 0x0B4, 0x0EE, 0x168, 0x132, 0x1DC, 0x186,
 286       0x2D0, 0x28A, 0x264, 0x23E, 0x3B8, 0x3E2, 0x30C, 0x356 },
 287     { 0x000, 0x05B, 0x0B6, 0x0ED, 0x16C, 0x137, 0x1DA, 0x181,
 288       0x2D8, 0x283, 0x26E, 0x235, 0x3B4, 0x3EF, 0x302, 0x359 },
 289     { 0x000, 0x05C, 0x0B8, 0x0E4, 0x170, 0x12C, 0x1C8, 0x194,
 290       0x2E0, 0x2BC, 0x258, 0x204, 0x390, 0x3CC, 0x328, 0x374 },
 291     { 0x000, 0x05D, 0x0BA, 0x0E7, 0x174, 0x129, 0x1CE, 0x193,
 292       0x2E8, 0x2B5, 0x252, 0x20F, 0x39C, 0x3C1, 0x326, 0x37B },
 293     { 0x000, 0x05E, 0x0BC, 0x0E2, 0x178, 0x126, 0x1C4, 0x19A,
 294       0x2F0, 0x2AE, 0x24C, 0x212, 0x388, 0x3D6, 0x334, 0x36A },
 295     { 0x000, 0x05F, 0x0BE, 0x0E1, 0x17C, 0x123, 0x1C2, 0x19D,
 296       0x2F8, 0x2A7, 0x246, 0x219, 0x384, 0x3DB, 0x33A, 0x365 },
 297     { 0x000, 0x060, 0x0C0, 0x0A0, 0x180, 0x1E0, 0x140, 0x120,
 298       0x300, 0x360, 0x3C0, 0x3A0, 0x280, 0x2E0, 0x240, 0x220 },
 299     { 0x000, 0x061, 0x0C2, 0x0A3, 0x184, 0x1E5, 0x146, 0x127,
 300       0x308, 0x369, 0x3CA, 0x3AB, 0x28C, 0x2ED, 0x24E, 0x22F },
 301     { 0x000, 0x062, 0x0C4, 0x0A6, 0x188, 0x1EA, 0x14C, 0x12E,
 302       0x310, 0x372, 0x3D4, 0x3B6, 0x298, 0x2FA, 0x25C, 0x23E },
 303     { 0x000, 0x063, 0x0C6, 0x0A5, 0x18C, 0x1EF, 0x14A, 0x129,
 304       0x318, 0x37B, 0x3DE, 0x3BD, 0x294, 0x2F7, 0x252, 0x231 },
 305     { 0x000, 0x064, 0x0C8, 0x0AC, 0x190, 0x1F4, 0x158, 0x13C,
 306       0x320, 0x344, 0x3E8, 0x38C, 0x2B0, 0x2D4, 0x278, 0x21C },
 307     { 0x000, 0x065, 0x0CA, 0x0AF, 0x194, 0x1F1, 0x15E, 0x13B,
 308       0x328, 0x34D, 0x3E2, 0x387, 0x2BC, 0x2D9, 0x276, 0x213 },
 309     { 0x000, 0x066, 0x0CC, 0x0AA, 0x198, 0x1FE, 0x154, 0x132,
 310       0x330, 0x356, 0x3FC, 0x39A, 0x2A8, 0x2CE, 0x264, 0x202 },
 311     { 0x000, 0x067, 0x0CE, 0x0A9, 0x19C, 0x1FB, 0x152, 0x135,
 312       0x338, 0x35F, 0x3F6, 0x391, 0x2A4, 0x2C3, 0x26A, 0x20D },
 313     { 0x000, 0x068, 0x0D0, 0x0B8, 0x1A0, 0x1C8, 0x170, 0x118,
 314       0x340, 0x328, 0x390, 0x3F8, 0x2E0, 0x288, 0x230, 0x258 },
 315     { 0x000, 0x069, 0x0D2, 0x0BB, 0x1A4, 0x1CD, 0x176, 0x11F,
 316       0x348, 0x321, 0x39A, 0x3F3, 0x2EC, 0x285, 0x23E, 0x257 },
 317     { 0x000, 0x06A, 0x0D4, 0x0BE, 0x1A8, 0x1C2, 0x17C, 0x116,
 318       0x350, 0x33A, 0x384, 0x3EE, 0x2F8, 0x292, 0x22C, 0x246 },
 319     { 0x000, 0x06B, 0x0D6, 0x0BD, 0x1AC, 0x1C7, 0x17A, 0x111,
 320       0x358, 0x333, 0x38E, 0x3E5, 0x2F4, 0x29F, 0x222, 0x249 },
 321     { 0x000, 0x06C, 0x0D8, 0x0B4, 0x1B0, 0x1DC, 0x168, 0x104,
 322       0x360, 0x30C, 0x3B8, 0x3D4, 0x2D0, 0x2BC, 0x208, 0x264 },
 323     { 0x000, 0x06D, 0x0DA, 0x0B7, 0x1B4, 0x1D9, 0x16E, 0x103,
 324       0x368, 0x305, 0x3B2, 0x3DF, 0x2DC, 0x2B1, 0x206, 0x26B },
 325     { 0x000, 0x06E, 0x0DC, 0x0B2, 0x1B8, 0x1D6, 0x164, 0x10A,
 326       0x370, 0x31E, 0x3AC, 0x3C2, 0x2C8, 0x2A6, 0x214, 0x27A },
 327     { 0x000, 0x06F, 0x0DE, 0x0B1, 0x1BC, 0x1D3, 0x162, 0x10D,
 328       0x378, 0x317, 0x3A6, 0x3C9, 0x2C4, 0x2AB, 0x21A, 0x275 },
 329     { 0x000, 0x070, 0x0E0, 0x090, 0x1C0, 0x1B0, 0x120, 0x150,
 330       0x380, 0x3F0, 0x360, 0x310, 0x240, 0x230, 0x2A0, 0x2D0 },
 331     { 0x000, 0x071, 0x0E2, 0x093, 0x1C4, 0x1B5, 0x126, 0x157,
 332       0x388, 0x3F9, 0x36A, 0x31B, 0x24C, 0x23D, 0x2AE, 0x2DF },
 333     { 0x000, 0x072, 0x0E4, 0x096, 0x1C8, 0x1BA, 0x12C, 0x15E,
 334       0x390, 0x3E2, 0x374, 0x306, 0x258, 0x22A, 0x2BC, 0x2CE },
 335     { 0x000, 0x073, 0x0E6, 0x095, 0x1CC, 0x1BF, 0x12A, 0x159,
 336       0x398, 0x3EB, 0x37E, 0x30D, 0x254, 0x227, 0x2B2, 0x2C1 },
 337     { 0x000, 0x074, 0x0E8, 0x09C, 0x1D0, 0x1A4, 0x138, 0x14C,
 338       0x3A0, 0x3D4, 0x348, 0x33C, 0x270, 0x204, 0x298, 0x2EC },
 339     { 0x000, 0x075, 0x0EA, 0x09F, 0x1D4, 0x1A1, 0x13E, 0x14B,
 340       0x3A8, 0x3DD, 0x342, 0x337, 0x27C, 0x209, 0x296, 0x2E3 },
 341     { 0x000, 0x076, 0x0EC, 0x09A, 0x1D8, 0x1AE, 0x134, 0x142,
 342       0x3B0, 0x3C6, 0x35C, 0x32A, 0x268, 0x21E, 0x284, 0x2F2 },
 343     { 0x000, 0x077, 0x0EE, 0x099, 0x1DC, 0x1AB, 0x132, 0x145,
 344       0x3B8, 0x3CF, 0x356, 0x321, 0x264, 0x213, 0x28A, 0x2FD },
 345     { 0x000, 0x078, 0x0F0, 0x088, 0x1E0, 0x198, 0x110, 0x168,
 346       0x3C0, 0x3B8, 0x330, 0x348, 0x220, 0x258, 0x2D0, 0x2A8 },
 347     { 0x000, 0x079, 0x0F2, 0x08B, 0x1E4, 0x19D, 0x116, 0x16F,
 348       0x3C8, 0x3B1, 0x33A, 0x343, 0x22C, 0x255, 0x2DE, 0x2A7 },
 349     { 0x000, 0x07A, 0x0F4, 0x08E, 0x1E8, 0x192, 0x11C, 0x166,
 350       0x3D0, 0x3AA, 0x324, 0x35E, 0x238, 0x242, 0x2CC, 0x2B6 },
 351     { 0x000, 0x07B, 0x0F6, 0x08D, 0x1EC, 0x197, 0x11A, 0x161,
 352       0x3D8, 0x3A3, 0x32E, 0x355, 0x234, 0x24F, 0x2C2, 0x2B9 },
 353     { 0x000, 0x07C, 0x0F8, 0x084, 0x1F0, 0x18C, 0x108, 0x174,
 354       0x3E0, 0x39C, 0x318, 0x364, 0x210, 0x26C, 0x2E8, 0x294 },
 355     { 0x000, 0x07D, 0x0FA, 0x087, 0x1F4, 0x189, 0x10E, 0x173,
 356       0x3E8, 0x395, 0x312, 0x36F, 0x21C, 0x261, 0x2E6, 0x29B },
 357     { 0x000, 0x07E, 0x0FC, 0x082, 0x1F8, 0x186, 0x104, 0x17A,
 358       0x3F0, 0x38E, 0x30C, 0x372, 0x208, 0x276, 0x2F4, 0x28A },
 359     { 0x000, 0x07F, 0x0FE, 0x081, 0x1FC, 0x183, 0x102, 0x17D,
 360       0x3F8, 0x387, 0x306, 0x379, 0x204, 0x27B, 0x2FA, 0x285 },
 361     { 0x000, 0x080, 0x100, 0x180, 0x200, 0x280, 0x300, 0x380,
 362       0x400, 0x480, 0x500, 0x580, 0x600, 0x680, 0x700, 0x780 },
 363     { 0x000, 0x081, 0x102, 0x183, 0x204, 0x285, 0x306, 0x387,
 364       0x408, 0x489, 0x50A, 0x58B, 0x60C, 0x68D, 0x70E, 0x78F },
 365     { 0x000, 0x082, 0x104, 0x186, 0x208, 0x28A, 0x30C, 0x38E,
 366       0x410, 0x492, 0x514, 0x596, 0x618, 0x69A, 0x71C, 0x79E },
 367     { 0x000, 0x083, 0x106, 0x185, 0x20C, 0x28F, 0x30A, 0x389,
 368       0x418, 0x49B, 0x51E, 0x59D, 0x614, 0x697, 0x712, 0x791 },
 369     { 0x000, 0x084, 0x108, 0x18C, 0x210, 0x294, 0x318, 0x39C,
 370       0x420, 0x4A4, 0x528, 0x5AC, 0x630, 0x6B4, 0x738, 0x7BC },
 371     { 0x000, 0x085, 0x10A, 0x18F, 0x214, 0x291, 0x31E, 0x39B,
 372       0x428, 0x4AD, 0x522, 0x5A7, 0x63C, 0x6B9, 0x736, 0x7B3 },
 373     { 0x000, 0x086, 0x10C, 0x18A, 0x218, 0x29E, 0x314, 0x392,
 374       0x430, 0x4B6, 0x53C, 0x5BA, 0x628, 0x6AE, 0x724, 0x7A2 },
 375     { 0x000, 0x087, 0x10E, 0x189, 0x21C, 0x29B, 0x312, 0x395,
 376       0x438, 0x4BF, 0x536, 0x5B1, 0x624, 0x6A3, 0x72A, 0x7AD },
 377     { 0x000, 0x088, 0x110, 0x198, 0x220, 0x2A8, 0x330, 0x3B8,
 378       0x440, 0x4C8, 0x550, 0x5D8, 0x660, 0x6E8, 0x770, 0x7F8 },
 379     { 0x000, 0x089, 0x112, 0x19B, 0x224, 0x2AD, 0x336, 0x3BF,
 380       0x448, 0x4C1, 0x55A, 0x5D3, 0x66C, 0x6E5, 0x77E, 0x7F7 },
 381     { 0x000, 0x08A, 0x114, 0x19E, 0x228, 0x2A2, 0x33C, 0x3B6,
 382       0x450, 0x4DA, 0x544, 0x5CE, 0x678, 0x6F2, 0x76C, 0x7E6 },
 383     { 0x000, 0x08B, 0x116, 0x19D, 0x22C, 0x2A7, 0x33A, 0x3B1,
 384       0x458, 0x4D3, 0x54E, 0x5C5, 0x674, 0x6FF, 0x762, 0x7E9 },
 385     { 0x000, 0x08C, 0x118, 0x194, 0x230, 0x2BC, 0x328, 0x3A4,
 386       0x460, 0x4EC, 0x578, 0x5F4, 0x650, 0x6DC, 0x748, 0x7C4 },
 387     { 0x000, 0x08D, 0x11A, 0x197, 0x234, 0x2B9, 0x32E, 0x3A3,
 388       0x468, 0x4E5, 0x572, 0x5FF, 0x65C, 0x6D1, 0x746, 0x7CB },
 389     { 0x000, 0x08E, 0x11C, 0x192, 0x238, 0x2B6, 0x324, 0x3AA,
 390       0x470, 0x4FE, 0x56C, 0x5E2, 0x648, 0x6C6, 0x754, 0x7DA },
 391     { 0x000, 0x08F, 0x11E, 0x191, 0x23C, 0x2B3, 0x322, 0x3AD,
 392       0x478, 0x4F7, 0x566, 0x5E9, 0x644, 0x6CB, 0x75A, 0x7D5 },
 393     { 0x000, 0x090, 0x120, 0x1B0, 0x240, 0x2D0, 0x360, 0x3F0,
 394       0x480, 0x410, 0x5A0, 0x530, 0x6C0, 0x650, 0x7E0, 0x770 },
 395     { 0x000, 0x091, 0x122, 0x1B3, 0x244, 0x2D5, 0x366, 0x3F7,
 396       0x488, 0x419, 0x5AA, 0x53B, 0x6CC, 0x65D, 0x7EE, 0x77F },
 397     { 0x000, 0x092, 0x124, 0x1B6, 0x248, 0x2DA, 0x36C, 0x3FE,
 398       0x490, 0x402, 0x5B4, 0x526, 0x6D8, 0x64A, 0x7FC, 0x76E },
 399     { 0x000, 0x093, 0x126, 0x1B5, 0x24C, 0x2DF, 0x36A, 0x3F9,
 400       0x498, 0x40B, 0x5BE, 0x52D, 0x6D4, 0x647, 0x7F2, 0x761 },
 401     { 0x000, 0x094, 0x128, 0x1BC, 0x250, 0x2C4, 0x378, 0x3EC,
 402       0x4A0, 0x434, 0x588, 0x51C, 0x6F0, 0x664, 0x7D8, 0x74C },
 403     { 0x000, 0x095, 0x12A, 0x1BF, 0x254, 0x2C1, 0x37E, 0x3EB,
 404       0x4A8, 0x43D, 0x582, 0x517, 0x6FC, 0x669, 0x7D6, 0x743 },
 405     { 0x000, 0x096, 0x12C, 0x1BA, 0x258, 0x2CE, 0x374, 0x3E2,
 406       0x4B0, 0x426, 0x59C, 0x50A, 0x6E8, 0x67E, 0x7C4, 0x752 },
 407     { 0x000, 0x097, 0x12E, 0x1B9, 0x25C, 0x2CB, 0x372, 0x3E5,
 408       0x4B8, 0x42F, 0x596, 0x501, 0x6E4, 0x673, 0x7CA, 0x75D },
 409     { 0x000, 0x098, 0x130, 0x1A8, 0x260, 0x2F8, 0x350, 0x3C8,
 410       0x4C0, 0x458, 0x5F0, 0x568, 0x6A0, 0x638, 0x790, 0x708 },
 411     { 0x000, 0x099, 0x132, 0x1AB, 0x264, 0x2FD, 0x356, 0x3CF,
 412       0x4C8, 0x451, 0x5FA, 0x563, 0x6AC, 0x635, 0x79E, 0x707 },
 413     { 0x000, 0x09A, 0x134, 0x1AE, 0x268, 0x2F2, 0x35C, 0x3C6,
 414       0x4D0, 0x44A, 0x5E4, 0x57E, 0x6B8, 0x622, 0x78C, 0x716 },
 415     { 0x000, 0x09B, 0x136, 0x1AD, 0x26C, 0x2F7, 0x35A, 0x3C1,
 416       0x4D8, 0x443, 0x5EE, 0x575, 0x6B4, 0x62F, 0x782, 0x719 },
 417     { 0x000, 0x09C, 0x138, 0x1A4, 0x270, 0x2EC, 0x348, 0x3D4,
 418       0x4E0, 0x47C, 0x5D8, 0x544, 0x690, 0x60C, 0x7A8, 0x734 },
 419     { 0x000, 0x09D, 0x13A, 0x1A7, 0x274, 0x2E9, 0x34E, 0x3D3,
 420       0x4E8, 0x475, 0x5D2, 0x54F, 0x69C, 0x601, 0x7A6, 0x73B },
 421     { 0x000, 0x09E, 0x13C, 0x1A2, 0x278, 0x2E6, 0x344, 0x3DA,
 422       0x4F0, 0x46E, 0x5CC, 0x552, 0x688, 0x616, 0x7B4, 0x72A },
 423     { 0x000, 0x09F, 0x13E, 0x1A1, 0x27C, 0x2E3, 0x342, 0x3DD,
 424       0x4F8, 0x467, 0x5C6, 0x559, 0x684, 0x61B, 0x7BA, 0x725 },
 425     { 0x000, 0x0A0, 0x140, 0x1E0, 0x280, 0x220, 0x3C0, 0x360,
 426       0x500, 0x5A0, 0x440, 0x4E0, 0x780, 0x720, 0x6C0, 0x660 },
 427     { 0x000, 0x0A1, 0x142, 0x1E3, 0x284, 0x225, 0x3C6, 0x367,
 428       0x508, 0x5A9, 0x44A, 0x4EB, 0x78C, 0x72D, 0x6CE, 0x66F },
 429     { 0x000, 0x0A2, 0x144, 0x1E6, 0x288, 0x22A, 0x3CC, 0x36E,
 430       0x510, 0x5B2, 0x454, 0x4F6, 0x798, 0x73A, 0x6DC, 0x67E },
 431     { 0x000, 0x0A3, 0x146, 0x1E5, 0x28C, 0x22F, 0x3CA, 0x369,
 432       0x518, 0x5BB, 0x45E, 0x4FD, 0x794, 0x737, 0x6D2, 0x671 },
 433     { 0x000, 0x0A4, 0x148, 0x1EC, 0x290, 0x234, 0x3D8, 0x37C,
 434       0x520, 0x584, 0x468, 0x4CC, 0x7B0, 0x714, 0x6F8, 0x65C },
 435     { 0x000, 0x0A5, 0x14A, 0x1EF, 0x294, 0x231, 0x3DE, 0x37B,
 436       0x528, 0x58D, 0x462, 0x4C7, 0x7BC, 0x719, 0x6F6, 0x653 },
 437     { 0x000, 0x0A6, 0x14C, 0x1EA, 0x298, 0x23E, 0x3D4, 0x372,
 438       0x530, 0x596, 0x47C, 0x4DA, 0x7A8, 0x70E, 0x6E4, 0x642 },
 439     { 0x000, 0x0A7, 0x14E, 0x1E9, 0x29C, 0x23B, 0x3D2, 0x375,
 440       0x538, 0x59F, 0x476, 0x4D1, 0x7A4, 0x703, 0x6EA, 0x64D },
 441     { 0x000, 0x0A8, 0x150, 0x1F8, 0x2A0, 0x208, 0x3F0, 0x358,
 442       0x540, 0x5E8, 0x410, 0x4B8, 0x7E0, 0x748, 0x6B0, 0x618 },
 443     { 0x000, 0x0A9, 0x152, 0x1FB, 0x2A4, 0x20D, 0x3F6, 0x35F,
 444       0x548, 0x5E1, 0x41A, 0x4B3, 0x7EC, 0x745, 0x6BE, 0x617 },
 445     { 0x000, 0x0AA, 0x154, 0x1FE, 0x2A8, 0x202, 0x3FC, 0x356,
 446       0x550, 0x5FA, 0x404, 0x4AE, 0x7F8, 0x752, 0x6AC, 0x606 },
 447     { 0x000, 0x0AB, 0x156, 0x1FD, 0x2AC, 0x207, 0x3FA, 0x351,
 448       0x558, 0x5F3, 0x40E, 0x4A5, 0x7F4, 0x75F, 0x6A2, 0x609 },
 449     { 0x000, 0x0AC, 0x158, 0x1F4, 0x2B0, 0x21C, 0x3E8, 0x344,
 450       0x560, 0x5CC, 0x438, 0x494, 0x7D0, 0x77C, 0x688, 0x624 },
 451     { 0x000, 0x0AD, 0x15A, 0x1F7, 0x2B4, 0x219, 0x3EE, 0x343,
 452       0x568, 0x5C5, 0x432, 0x49F, 0x7DC, 0x771, 0x686, 0x62B },
 453     { 0x000, 0x0AE, 0x15C, 0x1F2, 0x2B8, 0x216, 0x3E4, 0x34A,
 454       0x570, 0x5DE, 0x42C, 0x482, 0x7C8, 0x766, 0x694, 0x63A },
 455     { 0x000, 0x0AF, 0x15E, 0x1F1, 0x2BC, 0x213, 0x3E2, 0x34D,
 456       0x578, 0x5D7, 0x426, 0x489, 0x7C4, 0x76B, 0x69A, 0x635 },
 457     { 0x000, 0x0B0, 0x160, 0x1D0, 0x2C0, 0x270, 0x3A0, 0x310,
 458       0x580, 0x530, 0x4E0, 0x450, 0x740, 0x7F0, 0x620, 0x690 },
 459     { 0x000, 0x0B1, 0x162, 0x1D3, 0x2C4, 0x275, 0x3A6, 0x317,
 460       0x588, 0x539, 0x4EA, 0x45B, 0x74C, 0x7FD, 0x62E, 0x69F },
 461     { 0x000, 0x0B2, 0x164, 0x1D6, 0x2C8, 0x27A, 0x3AC, 0x31E,
 462       0x590, 0x522, 0x4F4, 0x446, 0x758, 0x7EA, 0x63C, 0x68E },
 463     { 0x000, 0x0B3, 0x166, 0x1D5, 0x2CC, 0x27F, 0x3AA, 0x319,
 464       0x598, 0x52B, 0x4FE, 0x44D, 0x754, 0x7E7, 0x632, 0x681 },
 465     { 0x000, 0x0B4, 0x168, 0x1DC, 0x2D0, 0x264, 0x3B8, 0x30C,
 466       0x5A0, 0x514, 0x4C8, 0x47C, 0x770, 0x7C4, 0x618, 0x6AC },
 467     { 0x000, 0x0B5, 0x16A, 0x1DF, 0x2D4, 0x261, 0x3BE, 0x30B,
 468       0x5A8, 0x51D, 0x4C2, 0x477, 0x77C, 0x7C9, 0x616, 0x6A3 },
 469     { 0x000, 0x0B6, 0x16C, 0x1DA, 0x2D8, 0x26E, 0x3B4, 0x302,
 470       0x5B0, 0x506, 0x4DC, 0x46A, 0x768, 0x7DE, 0x604, 0x6B2 },
 471     { 0x000, 0x0B7, 0x16E, 0x1D9, 0x2DC, 0x26B, 0x3B2, 0x305,
 472       0x5B8, 0x50F, 0x4D6, 0x461, 0x764, 0x7D3, 0x60A, 0x6BD },
 473     { 0x000, 0x0B8, 0x170, 0x1C8, 0x2E0, 0x258, 0x390, 0x328,
 474       0x5C0, 0x578, 0x4B0, 0x408, 0x720, 0x798, 0x650, 0x6E8 },
 475     { 0x000, 0x0B9, 0x172, 0x1CB, 0x2E4, 0x25D, 0x396, 0x32F,
 476       0x5C8, 0x571, 0x4BA, 0x403, 0x72C, 0x795, 0x65E, 0x6E7 },
 477     { 0x000, 0x0BA, 0x174, 0x1CE, 0x2E8, 0x252, 0x39C, 0x326,
 478       0x5D0, 0x56A, 0x4A4, 0x41E, 0x738, 0x782, 0x64C, 0x6F6 },
 479     { 0x000, 0x0BB, 0x176, 0x1CD, 0x2EC, 0x257, 0x39A, 0x321,
 480       0x5D8, 0x563, 0x4AE, 0x415, 0x734, 0x78F, 0x642, 0x6F9 },
 481     { 0x000, 0x0BC, 0x178, 0x1C4, 0x2F0, 0x24C, 0x388, 0x334,
 482       0x5E0, 0x55C, 0x498, 0x424, 0x710, 0x7AC, 0x668, 0x6D4 },
 483     { 0x000, 0x0BD, 0x17A, 0x1C7, 0x2F4, 0x249, 0x38E, 0x333,
 484       0x5E8, 0x555, 0x492, 0x42F, 0x71C, 0x7A1, 0x666, 0x6DB },
 485     { 0x000, 0x0BE, 0x17C, 0x1C2, 0x2F8, 0x246, 0x384, 0x33A,
 486       0x5F0, 0x54E, 0x48C, 0x432, 0x708, 0x7B6, 0x674, 0x6CA },
 487     { 0x000, 0x0BF, 0x17E, 0x1C1, 0x2FC, 0x243, 0x382, 0x33D,
 488       0x5F8, 0x547, 0x486, 0x439, 0x704, 0x7BB, 0x67A, 0x6C5 },
 489     { 0x000, 0x0C0, 0x180, 0x140, 0x300, 0x3C0, 0x280, 0x240,
 490       0x600, 0x6C0, 0x780, 0x740, 0x500, 0x5C0, 0x480, 0x440 },
 491     { 0x000, 0x0C1, 0x182, 0x143, 0x304, 0x3C5, 0x286, 0x247,
 492       0x608, 0x6C9, 0x78A, 0x74B, 0x50C, 0x5CD, 0x48E, 0x44F },
 493     { 0x000, 0x0C2, 0x184, 0x146, 0x308, 0x3CA, 0x28C, 0x24E,
 494       0x610, 0x6D2, 0x794, 0x756, 0x518, 0x5DA, 0x49C, 0x45E },
 495     { 0x000, 0x0C3, 0x186, 0x145, 0x30C, 0x3CF, 0x28A, 0x249,
 496       0x618, 0x6DB, 0x79E, 0x75D, 0x514, 0x5D7, 0x492, 0x451 },
 497     { 0x000, 0x0C4, 0x188, 0x14C, 0x310, 0x3D4, 0x298, 0x25C,
 498       0x620, 0x6E4, 0x7A8, 0x76C, 0x530, 0x5F4, 0x4B8, 0x47C },
 499     { 0x000, 0x0C5, 0x18A, 0x14F, 0x314, 0x3D1, 0x29E, 0x25B,
 500       0x628, 0x6ED, 0x7A2, 0x767, 0x53C, 0x5F9, 0x4B6, 0x473 },
 501     { 0x000, 0x0C6, 0x18C, 0x14A, 0x318, 0x3DE, 0x294, 0x252,
 502       0x630, 0x6F6, 0x7BC, 0x77A, 0x528, 0x5EE, 0x4A4, 0x462 },
 503     { 0x000, 0x0C7, 0x18E, 0x149, 0x31C, 0x3DB, 0x292, 0x255,
 504       0x638, 0x6FF, 0x7B6, 0x771, 0x524, 0x5E3, 0x4AA, 0x46D },
 505     { 0x000, 0x0C8, 0x190, 0x158, 0x320, 0x3E8, 0x2B0, 0x278,
 506       0x640, 0x688, 0x7D0, 0x718, 0x560, 0x5A8, 0x4F0, 0x438 },
 507     { 0x000, 0x0C9, 0x192, 0x15B, 0x324, 0x3ED, 0x2B6, 0x27F,
 508       0x648, 0x681, 0x7DA, 0x713, 0x56C, 0x5A5, 0x4FE, 0x437 },
 509     { 0x000, 0x0CA, 0x194, 0x15E, 0x328, 0x3E2, 0x2BC, 0x276,
 510       0x650, 0x69A, 0x7C4, 0x70E, 0x578, 0x5B2, 0x4EC, 0x426 },
 511     { 0x000, 0x0CB, 0x196, 0x15D, 0x32C, 0x3E7, 0x2BA, 0x271,
 512       0x658, 0x693, 0x7CE, 0x705, 0x574, 0x5BF, 0x4E2, 0x429 },
 513     { 0x000, 0x0CC, 0x198, 0x154, 0x330, 0x3FC, 0x2A8, 0x264,
 514       0x660, 0x6AC, 0x7F8, 0x734, 0x550, 0x59C, 0x4C8, 0x404 },
 515     { 0x000, 0x0CD, 0x19A, 0x157, 0x334, 0x3F9, 0x2AE, 0x263,
 516       0x668, 0x6A5, 0x7F2, 0x73F, 0x55C, 0x591, 0x4C6, 0x40B },
 517     { 0x000, 0x0CE, 0x19C, 0x152, 0x338, 0x3F6, 0x2A4, 0x26A,
 518       0x670, 0x6BE, 0x7EC, 0x722, 0x548, 0x586, 0x4D4, 0x41A },
 519     { 0x000, 0x0CF, 0x19E, 0x151, 0x33C, 0x3F3, 0x2A2, 0x26D,
 520       0x678, 0x6B7, 0x7E6, 0x729, 0x544, 0x58B, 0x4DA, 0x415 },
 521     { 0x000, 0x0D0, 0x1A0, 0x170, 0x340, 0x390, 0x2E0, 0x230,
 522       0x680, 0x650, 0x720, 0x7F0, 0x5C0, 0x510, 0x460, 0x4B0 },
 523     { 0x000, 0x0D1, 0x1A2, 0x173, 0x344, 0x395, 0x2E6, 0x237,
 524       0x688, 0x659, 0x72A, 0x7FB, 0x5CC, 0x51D, 0x46E, 0x4BF },
 525     { 0x000, 0x0D2, 0x1A4, 0x176, 0x348, 0x39A, 0x2EC, 0x23E,
 526       0x690, 0x642, 0x734, 0x7E6, 0x5D8, 0x50A, 0x47C, 0x4AE },
 527     { 0x000, 0x0D3, 0x1A6, 0x175, 0x34C, 0x39F, 0x2EA, 0x239,
 528       0x698, 0x64B, 0x73E, 0x7ED, 0x5D4, 0x507, 0x472, 0x4A1 },
 529     { 0x000, 0x0D4, 0x1A8, 0x17C, 0x350, 0x384, 0x2F8, 0x22C,
 530       0x6A0, 0x674, 0x708, 0x7DC, 0x5F0, 0x524, 0x458, 0x48C },
 531     { 0x000, 0x0D5, 0x1AA, 0x17F, 0x354, 0x381, 0x2FE, 0x22B,
 532       0x6A8, 0x67D, 0x702, 0x7D7, 0x5FC, 0x529, 0x456, 0x483 },
 533     { 0x000, 0x0D6, 0x1AC, 0x17A, 0x358, 0x38E, 0x2F4, 0x222,
 534       0x6B0, 0x666, 0x71C, 0x7CA, 0x5E8, 0x53E, 0x444, 0x492 },
 535     { 0x000, 0x0D7, 0x1AE, 0x179, 0x35C, 0x38B, 0x2F2, 0x225,
 536       0x6B8, 0x66F, 0x716, 0x7C1, 0x5E4, 0x533, 0x44A, 0x49D },
 537     { 0x000, 0x0D8, 0x1B0, 0x168, 0x360, 0x3B8, 0x2D0, 0x208,
 538       0x6C0, 0x618, 0x770, 0x7A8, 0x5A0, 0x578, 0x410, 0x4C8 },
 539     { 0x000, 0x0D9, 0x1B2, 0x16B, 0x364, 0x3BD, 0x2D6, 0x20F,
 540       0x6C8, 0x611, 0x77A, 0x7A3, 0x5AC, 0x575, 0x41E, 0x4C7 },
 541     { 0x000, 0x0DA, 0x1B4, 0x16E, 0x368, 0x3B2, 0x2DC, 0x206,
 542       0x6D0, 0x60A, 0x764, 0x7BE, 0x5B8, 0x562, 0x40C, 0x4D6 },
 543     { 0x000, 0x0DB, 0x1B6, 0x16D, 0x36C, 0x3B7, 0x2DA, 0x201,
 544       0x6D8, 0x603, 0x76E, 0x7B5, 0x5B4, 0x56F, 0x402, 0x4D9 },
 545     { 0x000, 0x0DC, 0x1B8, 0x164, 0x370, 0x3AC, 0x2C8, 0x214,
 546       0x6E0, 0x63C, 0x758, 0x784, 0x590, 0x54C, 0x428, 0x4F4 },
 547     { 0x000, 0x0DD, 0x1BA, 0x167, 0x374, 0x3A9, 0x2CE, 0x213,
 548       0x6E8, 0x635, 0x752, 0x78F, 0x59C, 0x541, 0x426, 0x4FB },
 549     { 0x000, 0x0DE, 0x1BC, 0x162, 0x378, 0x3A6, 0x2C4, 0x21A,
 550       0x6F0, 0x62E, 0x74C, 0x792, 0x588, 0x556, 0x434, 0x4EA },
 551     { 0x000, 0x0DF, 0x1BE, 0x161, 0x37C, 0x3A3, 0x2C2, 0x21D,
 552       0x6F8, 0x627, 0x746, 0x799, 0x584, 0x55B, 0x43A, 0x4E5 },
 553     { 0x000, 0x0E0, 0x1C0, 0x120, 0x380, 0x360, 0x240, 0x2A0,
 554       0x700, 0x7E0, 0x6C0, 0x620, 0x480, 0x460, 0x540, 0x5A0 },
 555     { 0x000, 0x0E1, 0x1C2, 0x123, 0x384, 0x365, 0x246, 0x2A7,
 556       0x708, 0x7E9, 0x6CA, 0x62B, 0x48C, 0x46D, 0x54E, 0x5AF },
 557     { 0x000, 0x0E2, 0x1C4, 0x126, 0x388, 0x36A, 0x24C, 0x2AE,
 558       0x710, 0x7F2, 0x6D4, 0x636, 0x498, 0x47A, 0x55C, 0x5BE },
 559     { 0x000, 0x0E3, 0x1C6, 0x125, 0x38C, 0x36F, 0x24A, 0x2A9,
 560       0x718, 0x7FB, 0x6DE, 0x63D, 0x494, 0x477, 0x552, 0x5B1 },
 561     { 0x000, 0x0E4, 0x1C8, 0x12C, 0x390, 0x374, 0x258, 0x2BC,
 562       0x720, 0x7C4, 0x6E8, 0x60C, 0x4B0, 0x454, 0x578, 0x59C },
 563     { 0x000, 0x0E5, 0x1CA, 0x12F, 0x394, 0x371, 0x25E, 0x2BB,
 564       0x728, 0x7CD, 0x6E2, 0x607, 0x4BC, 0x459, 0x576, 0x593 },
 565     { 0x000, 0x0E6, 0x1CC, 0x12A, 0x398, 0x37E, 0x254, 0x2B2,
 566       0x730, 0x7D6, 0x6FC, 0x61A, 0x4A8, 0x44E, 0x564, 0x582 },
 567     { 0x000, 0x0E7, 0x1CE, 0x129, 0x39C, 0x37B, 0x252, 0x2B5,
 568       0x738, 0x7DF, 0x6F6, 0x611, 0x4A4, 0x443, 0x56A, 0x58D },
 569     { 0x000, 0x0E8, 0x1D0, 0x138, 0x3A0, 0x348, 0x270, 0x298,
 570       0x740, 0x7A8, 0x690, 0x678, 0x4E0, 0x408, 0x530, 0x5D8 },
 571     { 0x000, 0x0E9, 0x1D2, 0x13B, 0x3A4, 0x34D, 0x276, 0x29F,
 572       0x748, 0x7A1, 0x69A, 0x673, 0x4EC, 0x405, 0x53E, 0x5D7 },
 573     { 0x000, 0x0EA, 0x1D4, 0x13E, 0x3A8, 0x342, 0x27C, 0x296,
 574       0x750, 0x7BA, 0x684, 0x66E, 0x4F8, 0x412, 0x52C, 0x5C6 },
 575     { 0x000, 0x0EB, 0x1D6, 0x13D, 0x3AC, 0x347, 0x27A, 0x291,
 576       0x758, 0x7B3, 0x68E, 0x665, 0x4F4, 0x41F, 0x522, 0x5C9 },
 577     { 0x000, 0x0EC, 0x1D8, 0x134, 0x3B0, 0x35C, 0x268, 0x284,
 578       0x760, 0x78C, 0x6B8, 0x654, 0x4D0, 0x43C, 0x508, 0x5E4 },
 579     { 0x000, 0x0ED, 0x1DA, 0x137, 0x3B4, 0x359, 0x26E, 0x283,
 580       0x768, 0x785, 0x6B2, 0x65F, 0x4DC, 0x431, 0x506, 0x5EB },
 581     { 0x000, 0x0EE, 0x1DC, 0x132, 0x3B8, 0x356, 0x264, 0x28A,
 582       0x770, 0x79E, 0x6AC, 0x642, 0x4C8, 0x426, 0x514, 0x5FA },
 583     { 0x000, 0x0EF, 0x1DE, 0x131, 0x3BC, 0x353, 0x262, 0x28D,
 584       0x778, 0x797, 0x6A6, 0x649, 0x4C4, 0x42B, 0x51A, 0x5F5 },
 585     { 0x000, 0x0F0, 0x1E0, 0x110, 0x3C0, 0x330, 0x220, 0x2D0,
 586       0x780, 0x770, 0x660, 0x690, 0x440, 0x4B0, 0x5A0, 0x550 },
 587     { 0x000, 0x0F1, 0x1E2, 0x113, 0x3C4, 0x335, 0x226, 0x2D7,
 588       0x788, 0x779, 0x66A, 0x69B, 0x44C, 0x4BD, 0x5AE, 0x55F },
 589     { 0x000, 0x0F2, 0x1E4, 0x116, 0x3C8, 0x33A, 0x22C, 0x2DE,
 590       0x790, 0x762, 0x674, 0x686, 0x458, 0x4AA, 0x5BC, 0x54E },
 591     { 0x000, 0x0F3, 0x1E6, 0x115, 0x3CC, 0x33F, 0x22A, 0x2D9,
 592       0x798, 0x76B, 0x67E, 0x68D, 0x454, 0x4A7, 0x5B2, 0x541 },
 593     { 0x000, 0x0F4, 0x1E8, 0x11C, 0x3D0, 0x324, 0x238, 0x2CC,
 594       0x7A0, 0x754, 0x648, 0x6BC, 0x470, 0x484, 0x598, 0x56C },
 595     { 0x000, 0x0F5, 0x1EA, 0x11F, 0x3D4, 0x321, 0x23E, 0x2CB,
 596       0x7A8, 0x75D, 0x642, 0x6B7, 0x47C, 0x489, 0x596, 0x563 },
 597     { 0x000, 0x0F6, 0x1EC, 0x11A, 0x3D8, 0x32E, 0x234, 0x2C2,
 598       0x7B0, 0x746, 0x65C, 0x6AA, 0x468, 0x49E, 0x584, 0x572 },
 599     { 0x000, 0x0F7, 0x1EE, 0x119, 0x3DC, 0x32B, 0x232, 0x2C5,
 600       0x7B8, 0x74F, 0x656, 0x6A1, 0x464, 0x493, 0x58A, 0x57D },
 601     { 0x000, 0x0F8, 0x1F0, 0x108, 0x3E0, 0x318, 0x210, 0x2E8,
 602       0x7C0, 0x738, 0x630, 0x6C8, 0x420, 0x4D8, 0x5D0, 0x528 },
 603     { 0x000, 0x0F9, 0x1F2, 0x10B, 0x3E4, 0x31D, 0x216, 0x2EF,
 604       0x7C8, 0x731, 0x63A, 0x6C3, 0x42C, 0x4D5, 0x5DE, 0x527 },
 605     { 0x000, 0x0FA, 0x1F4, 0x10E, 0x3E8, 0x312, 0x21C, 0x2E6,
 606       0x7D0, 0x72A, 0x624, 0x6DE, 0x438, 0x4C2, 0x5CC, 0x536 },
 607     { 0x000, 0x0FB, 0x1F6, 0x10D, 0x3EC, 0x317, 0x21A, 0x2E1,
 608       0x7D8, 0x723, 0x62E, 0x6D5, 0x434, 0x4CF, 0x5C2, 0x539 },
 609     { 0x000, 0x0FC, 0x1F8, 0x104, 0x3F0, 0x30C, 0x208, 0x2F4,
 610       0x7E0, 0x71C, 0x618, 0x6E4, 0x410, 0x4EC, 0x5E8, 0x514 },
 611     { 0x000, 0x0FD, 0x1FA, 0x107, 0x3F4, 0x309, 0x20E, 0x2F3,
 612       0x7E8, 0x715, 0x612, 0x6EF, 0x41C, 0x4E1, 0x5E6, 0x51B },
 613     { 0x000, 0x0FE, 0x1FC, 0x102, 0x3F8, 0x306, 0x204, 0x2FA,
 614       0x7F0, 0x70E, 0x60C, 0x6F2, 0x408, 0x4F6, 0x5F4, 0x50A },
 615     { 0x000, 0x0FF, 0x1FE, 0x101, 0x3FC, 0x303, 0x202, 0x2FD,
 616       0x7F8, 0x707, 0x606, 0x6F9, 0x404, 0x4FB, 0x5FA, 0x505 }
 617   };
 618 // Generated in CLISP:
 619 // (dotimes (x 256)
 620 //   (dotimes (y 16)
 621 //     (let ((z 0))
 622 //       (dotimes (b 4) (when (logbitp b y) (setq z (logxor z (ash x b)))))
 623 //       (when (zerop (mod y 8)) (format t "~%   "))
 624 //       (format t " 0x~3,'0X," z))))
 625 #endif
 626
 627 // Multiply two GF2-polynomials of degree < 16.
 628 #if defined(__sparc__) || defined(__sparc64__)
 629 extern "C" uint32 gf2_mul16 (uint16 x, uint16 y);
 630 #else
 631 uint32 gf2_mul16 (uint16 x, uint16 y)
 632 {
 633         var uint16 *ptr; // uint16 ptr[0x10];
 634         var uint32 res = 0;
 635         // 8 table accesses.
 636         ptr = gf2_mul_table[x & 0xFF];
 637         res ^= (uint32)ptr[y & 0xF];
 638         res ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 639         res ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 640         res ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 641         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 642         res ^= (uint32)ptr[y & 0xF] << 8;
 643         res ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 644         res ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
 645         res ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
 646         return res;
 647 }
 648 #endif
 649
 650 // Multiply two GF2-polynomials of degree < 32.
 651 // Stores the low part, returns the high part.
 652 #if defined(__sparc__) || defined(__sparc64__)
 653 extern "C" uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo);
 654 #else
 655 uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo)
 656 {
 657         var uint16 *ptr; // uint16 ptr[0x10];
 658         var uint32 hi = 0;
 659         var uint32 lo = 0;
 660         var uint32 mid = 0;
 661         // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0).
 662 #if 0
 663         // Standard multiplication, 32 table accesses.
 664         ptr = gf2_mul_table[x & 0xFF];
 665         lo ^= (uint32)ptr[y & 0xF];
 666         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 667         lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 668         lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 669         mid ^= (uint32)ptr[(y >> 16) & 0xF];
 670         mid ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
 671         mid ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
 672         mid ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
 673         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 674         lo ^= (uint32)ptr[y & 0xF] << 8;
 675         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 676         mid ^= (uint32)ptr[(y >> 8) & 0xF];
 677         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 4;
 678         mid ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
 679         mid ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
 680         hi ^= (uint32)ptr[(y >> 24) & 0xF];
 681         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 4;
 682         ptr = gf2_mul_table[(x >> 16) & 0xFF];
 683         mid ^= (uint32)ptr[y & 0xF];
 684         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 685         mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 686         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 687         hi ^= (uint32)ptr[(y >> 16) & 0xF];
 688         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
 689         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
 690         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
 691         ptr = gf2_mul_table[(x >> 24) & 0xFF];
 692         mid ^= (uint32)ptr[y & 0xF] << 8;
 693         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 694         hi ^= (uint32)ptr[(y >> 8) & 0xF];
 695         hi ^= (uint32)ptr[(y >> 12) & 0xF] << 4;
 696         hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
 697         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
 698         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
 699         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
 700 #else
 701         // Apply Karatsuba:
 702         // lo := low16(x)*low16(y)
 703         // hi := high16(x)*high16(y)
 704         // mid := (high16(x)+low16(x))*(high16(y)+low16(y))
 705         // mid := mid + lo + hi
 706         // 24 table accesses.
 707         ptr = gf2_mul_table[x & 0xFF];
 708         lo ^= (uint32)ptr[y & 0xF];
 709         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 710         lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 711         lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 712         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 713         lo ^= (uint32)ptr[y & 0xF] << 8;
 714         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 715         lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
 716         lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
 717         ptr = gf2_mul_table[(x >> 16) & 0xFF];
 718         hi ^= (uint32)ptr[(y >> 16) & 0xF];
 719         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
 720         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
 721         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
 722         ptr = gf2_mul_table[(x >> 24) & 0xFF];
 723         hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
 724         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
 725         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
 726         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
 727         x ^= x >> 16;
 728         y ^= y >> 16;
 729         ptr = gf2_mul_table[x & 0xFF];
 730         mid ^= (uint32)ptr[y & 0xF];
 731         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 732         mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 733         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 734         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 735         mid ^= (uint32)ptr[y & 0xF] << 8;
 736         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 737         mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
 738         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
 739         mid ^= lo;
 740         mid ^= hi;
 741 #endif
 742         *plo = lo ^ (mid << 16);
 743         return hi ^ (mid >> 16);
 744 }
 745 #endif
 746
 747 // Multiply two GF2-polynomials of degree < intDsize.
 748 // Stores the low part, returns the high part.
 749 #if (intDsize==32)
 750   #define gf2_mul_uintD  gf2_mul32
 751 #endif
 752 #if (intDsize==64)
 753   inline uint64 gf2_mul32_ (uint32 x, uint32 y)
 754   {
 755         var uint16 *ptr; // uint16 ptr[0x10];
 756         var uint32 hi = 0;
 757         var uint32 lo = 0;
 758         var uint32 mid = 0;
 759         // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0).
 760         // Apply Karatsuba:
 761         // lo := low16(x)*low16(y)
 762         // hi := high16(x)*high16(y)
 763         // mid := (high16(x)+low16(x))*(high16(y)+low16(y))
 764         // mid := mid + lo + hi
 765         // 24 table accesses.
 766         ptr = gf2_mul_table[x & 0xFF];
 767         lo ^= (uint32)ptr[y & 0xF];
 768         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 769         lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 770         lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 771         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 772         lo ^= (uint32)ptr[y & 0xF] << 8;
 773         lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 774         lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
 775         lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
 776         ptr = gf2_mul_table[(x >> 16) & 0xFF];
 777         hi ^= (uint32)ptr[(y >> 16) & 0xF];
 778         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
 779         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
 780         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
 781         ptr = gf2_mul_table[(x >> 24) & 0xFF];
 782         hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
 783         hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
 784         hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
 785         hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
 786         x ^= x >> 16;
 787         y ^= y >> 16;
 788         ptr = gf2_mul_table[x & 0xFF];
 789         mid ^= (uint32)ptr[y & 0xF];
 790         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
 791         mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
 792         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
 793         ptr = gf2_mul_table[(x >> 8) & 0xFF];
 794         mid ^= (uint32)ptr[y & 0xF] << 8;
 795         mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
 796         mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
 797         mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
 798         mid ^= lo;
 799         mid ^= hi;
 800         return (((uint64)hi << 32) | ((uint64)lo)) ^ ((uint64)mid << 16);
 801   }
 802   static uintD gf2_mul_uintD (uintD x, uintD y, uintD* plo)
 803   {
 804         // Apply Karatsuba:
 805         // lo := low32(x)*low32(y)
 806         // hi := high32(x)*high32(y)
 807         // mid := (high32(x)+low32(x))*(high32(y)+low32(y))
 808         // mid := mid + lo + hi
 809         // 72 table accesses.
 810         var uint64 lo = gf2_mul32_(x,y);
 811         var uint64 hi = gf2_mul32_(x>>32,y>>32);
 812         var uint64 mid = gf2_mul32_(x^(x>>32),y^(y>>32));
 813         // Result will be (hi << 64) ^ (mid << 32) ^ (lo << 0).
 814         *plo = lo ^ (mid << 32);
 815         return hi ^ (mid >> 32);
 816   }
 817 #endif
 818
 819 static const _cl_UP gf2_mul (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
 820 {{
 821         DeclarePoly(cl_GV_MI,x);
 822         DeclarePoly(cl_GV_MI,y);
 823         var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
 824         var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
 825         var uintL xlen = xv->v.length();
 826         var uintL ylen = yv->v.length();
 827         if (xlen == 0)
 828                 return _cl_UP(UPR, x);
 829         if (ylen == 0)
 830                 return _cl_UP(UPR, y);
 831         var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
 832         var uintL len = xlen+ylen-1;
 833         var cl_GV_MI result = cl_GV_MI(len,R);
 834         var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
 835         xlen = ceiling(xlen,intDsize);
 836         ylen = ceiling(ylen,intDsize);
 837         if (xlen < ylen) {
 838                 var uintL xlen1 = ceiling(len,intDsize)-ylen; // = xlen-{0,1}
 839                 for (uintL i = 0; i < xlen; i++) {
 840                         var uintD xw = xv->data[i];
 841                         var uintD* rvptr = &rv->data[i];
 842                         var uintD carry = 0;
 843                         for (uintL j = 0; j < ylen; j++) {
 844                                 var uintD rwlo;
 845                                 var uintD rwhi
 846                                   = gf2_mul_uintD(xw,yv->data[j],&rwlo);
 847                                 *rvptr++ ^= carry ^ rwlo;
 848                                 carry = rwhi;
 849                         }
 850                         if (i < xlen1)
 851                                 *rvptr ^= carry;
 852                 }
 853         } else {
 854                 var uintL ylen1 = ceiling(len,intDsize)-xlen; // = ylen-{0,1}
 855                 for (uintL j = 0; j < ylen; j++) {
 856                         var uintD yw = yv->data[j];
 857                         var uintD* rvptr = &rv->data[j];
 858                         var uintD carry = 0;
 859                         for (uintL i = 0; i < xlen; i++) {
 860                                 var uintD rwlo;
 861                                 var uintD rwhi
 862                                   = gf2_mul_uintD(xv->data[i],yw,&rwlo);
 863                                 *rvptr++ ^= carry ^ rwlo;
 864                                 carry = rwhi;
 865                         }
 866                         if (j < ylen1)
 867                                 *rvptr ^= carry;
 868                 }
 869         }
 870         return _cl_UP(UPR, result);
 871 }}
 872
 873 // In characteristic 2, we square a polynomial by doubling the exponents:
 874 // (sum(a_i T^i))^2 = sum(a_i^2 T^2i) = sum(a_i T^2i).
 875
 876 static uint16 gf2_square_table[0x100] =
 877   {
 878     0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
 879     0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
 880     0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
 881     0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
 882     0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
 883     0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
 884     0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
 885     0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
 886     0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
 887     0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
 888     0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
 889     0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
 890     0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
 891     0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
 892     0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
 893     0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
 894     0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
 895     0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
 896     0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
 897     0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
 898     0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
 899     0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
 900     0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
 901     0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
 902     0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
 903     0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
 904     0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
 905     0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
 906     0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
 907     0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
 908     0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
 909     0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
 910   };
 911 // Generated in CLISP:
 912 // (dotimes (i 256)
 913 //   (let ((j 0))
 914 //     (dotimes (b 8) (when (logbitp b i) (setq j (logior j (ash 1 (+ b b))))))
 915 //     (when (zerop (mod i 8)) (format t "~%   "))
 916 //     (format t " 0x~4,'0X," j)))
 917
 918 // Square a GF2-polynomial of degree < intDsize.
 919 // Stores the low part, returns the high part.
 920 static uintD gf2_square_uintD (uintD x, uintD* lo)
 921 {
 922 #if (intDsize==32)
 923         *lo =   ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
 924               | (uintD)gf2_square_table[x & 0xFF];
 925         x = x>>16;
 926         return  ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
 927               | (uintD)gf2_square_table[x & 0xFF];
 928 #endif
 929 #if (intDsize==64)
 930         *lo =   ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48)
 931               | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32)
 932               | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
 933               | (uintD)gf2_square_table[x & 0xFF];
 934         x = x>>32;
 935         return  ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48)
 936               | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32)
 937               | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
 938               | (uintD)gf2_square_table[x & 0xFF];
 939 #endif
 940 }
 941
 942 static const _cl_UP gf2_square (cl_heap_univpoly_ring* UPR, const _cl_UP& x)
 943 {{
 944         DeclarePoly(cl_GV_MI,x);
 945         var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
 946         var uintL xlen = xv->v.length();
 947         if (xlen == 0)
 948                 return _cl_UP(UPR, x);
 949         var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
 950         var uintL len = 2*xlen-1;
 951         var cl_GV_MI result = cl_GV_MI(len,R);
 952         var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
 953         var uintL count = floor(xlen,intDsize);
 954         for (uintL i = 0; i < count; i++)
 955                 rv->data[2*i+1] = gf2_square_uintD(xv->data[i],&rv->data[2*i]);
 956         xlen = xlen%intDsize;
 957         if (xlen > 0) {
 958                 var uintD hiword = xv->data[count]; // xlen bits
 959                 hiword = gf2_square_uintD(hiword,&rv->data[2*count]);
 960                 if (xlen > intDsize/2)
 961                         rv->data[2*count+1] = hiword;
 962         }
 963         return _cl_UP(UPR, result);
 964 }}
 965
 966 // Scalar multiplication of GF(2)-polynomials is trivial: 0*y = 0, 1*y = y.
 967 static const _cl_UP gf2_scalmul (cl_heap_univpoly_ring* UPR, const cl_ring_element& x, const _cl_UP& y)
 968 {
 969         if (!(UPR->basering() == x.ring())) cl_abort();
 970  {
 971         DeclarePoly(_cl_MI,x);
 972         var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
 973         if (R->_zerop(x))
 974                 return _cl_UP(UPR, cl_null_GV_I);
 975         return y;
 976 }}
 977
 978 // Evaluation of GF(2)-polynomials is trivial:
 979 // At 0, it's the coefficient 0. At 1, it's the sum of all coefficients,
 980 // i.e. the parity of the number of nonzero coefficients.
 981 static const cl_ring_element gf2_eval (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const cl_ring_element& y)
 982 {{
 983         DeclarePoly(cl_GV_MI,x);
 984         if (!(UPR->basering() == y.ring())) cl_abort();
 985   {     DeclarePoly(_cl_MI,y);
 986         var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
 987         var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
 988         var uintL len = xv->v.length();
 989         if (len==0)
 990                 return R->zero();
 991         if (R->_zerop(y))
 992                 return cl_MI(R, x[0]);
 993         else {
 994                 var uintL count = ceiling(len,intDsize);
 995                 var uintL bitcount = 0;
 996                 do {
 997                         count--;
 998                         bitcount += logcountD(xv->data[count]);
 999                 } while (count > 0);
1000                 return R->canonhom(bitcount%2);
1001         }
1002 }}}
1003
1004 static cl_univpoly_setops gf2_setops = {
1005         modint_fprint,
1006         gf2_equal
1007 };
1008
1009 static cl_univpoly_addops gf2_addops = {
1010         modint_zero,
1011         modint_zerop,
1012         gf2_plus,
1013         gf2_minus,
1014         gf2_uminus
1015 };
1016
1017 static cl_univpoly_mulops gf2_mulops = {
1018         modint_one,
1019         modint_canonhom,
1020         gf2_mul,
1021         gf2_square,
1022         modint_exptpos
1023 };
1024
1025 static cl_univpoly_modulops gf2_modulops = {
1026         gf2_scalmul
1027 };
1028
1029 static cl_univpoly_polyops gf2_polyops = {
1030         modint_degree,
1031         modint_ldegree,
1032         modint_monomial,
1033         modint_coeff,
1034         modint_create,
1035         modint_set_coeff,
1036         modint_finalize,
1037         gf2_eval
1038 };
1039
1040 class cl_heap_gf2_univpoly_ring : public cl_heap_univpoly_ring {
1041         SUBCLASS_cl_heap_univpoly_ring()
1042 public:
1043         // Constructor.
1044         cl_heap_gf2_univpoly_ring (const cl_ring& r)
1045                 : cl_heap_univpoly_ring (r, &gf2_setops, &gf2_addops, &gf2_mulops, &gf2_modulops, &gf2_polyops) {}
1046 };
1047
1048 }  // namespace cln