src/polynomial/elem/cl_UP_GF2.h

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