// Univariate Polynomials over the ring GF(2) = Z/2Z. #include "cln/GV_modinteger.h" #include "cln/modinteger.h" #include "cln/GV_integer.h" #include "cl_DS.h" #include "cln/abort.h" namespace cln { // This is actually defined in cl_GV_I.cc (*ugh*). struct cl_heap_GV_I_bits1 : public cl_heap_GV_I { uintD data[1]; }; static cl_boolean gf2_equal (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y) {{ DeclarePoly(cl_GV_MI,x); DeclarePoly(cl_GV_MI,y); unused UPR; var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer; var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer; var uintL xlen = xv->v.length(); var uintL ylen = yv->v.length(); if (!(xlen == ylen)) return cl_false; // We can compare full words since unused bits in the last word are 0. var uintL count = ceiling(xlen,intDsize); if (compare_loop_up(xv->data,yv->data,count) != 0) return cl_false; return cl_true; }} static const _cl_UP gf2_plus (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y) {{ DeclarePoly(cl_GV_MI,x); DeclarePoly(cl_GV_MI,y); var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer; var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer; var uintL xlen = xv->v.length(); var uintL ylen = yv->v.length(); if (xlen == 0) return _cl_UP(UPR, y); if (ylen == 0) return _cl_UP(UPR, x); // Now xlen > 0, ylen > 0. var cl_heap_modint_ring* R = TheModintRing(UPR->basering()); if (xlen > ylen) { var cl_GV_MI result = cl_GV_MI(xlen,R); var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer; // Copy xv into rv. copy_loop_up(xv->data,rv->data,ceiling(xlen,intDsize)); // Add yv to rv. xor_loop_up(rv->data,yv->data,ceiling(ylen,intDsize)); return _cl_UP(UPR, result); } if (xlen < ylen) { var cl_GV_MI result = cl_GV_MI(ylen,R); var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer; // Copy yv into rv. copy_loop_up(yv->data,rv->data,ceiling(ylen,intDsize)); // Add xv to rv. xor_loop_up(rv->data,xv->data,ceiling(xlen,intDsize)); return _cl_UP(UPR, result); } // Now xlen = ylen > 0. Add and normalize simultaneously. for (;;) { var uintL index = floor(xlen-1,intDsize); var uintD rword = xv->data[index] ^ yv->data[index]; if (rword == 0) { xlen = index*intDsize; if (xlen == 0) return _cl_UP(UPR, cl_null_GV_I); } else { xlen = index*intDsize; integerlengthD(rword, xlen += ); // Build result. var cl_GV_MI result = cl_GV_MI(xlen,R); var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer; copy_loop_up(xv->data,rv->data,index); xor_loop_up(rv->data,yv->data,index); rv->data[index] = rword; return _cl_UP(UPR, result); } } }} // In characteristic 2, x-y = x+y. #define gf2_minus gf2_plus // In characteristic 2, -x = x. static const _cl_UP gf2_uminus (cl_heap_univpoly_ring* UPR, const _cl_UP& x) { unused UPR; return x; } #if !(defined(__sparc__) || defined(__sparc64__)) // Multiplication of polynomials over GF(2) can unfortunately not profit // from hardware multiply instructions. Use a table instead. // This is a 2^8 x 2^4 table. Maybe a 2^6 x 2^6 table would be better? // (LiDIA uses a 2^8 x 2^8 table, which is way too large.) static uint16 gf2_mul_table[0x100][0x10] = { { 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000 }, { 0x000, 0x001, 0x002, 0x003, 0x004, 0x005, 0x006, 0x007, 0x008, 0x009, 0x00A, 0x00B, 0x00C, 0x00D, 0x00E, 0x00F }, { 0x000, 0x002, 0x004, 0x006, 0x008, 0x00A, 0x00C, 0x00E, 0x010, 0x012, 0x014, 0x016, 0x018, 0x01A, 0x01C, 0x01E }, { 0x000, 0x003, 0x006, 0x005, 0x00C, 0x00F, 0x00A, 0x009, 0x018, 0x01B, 0x01E, 0x01D, 0x014, 0x017, 0x012, 0x011 }, { 0x000, 0x004, 0x008, 0x00C, 0x010, 0x014, 0x018, 0x01C, 0x020, 0x024, 0x028, 0x02C, 0x030, 0x034, 0x038, 0x03C }, { 0x000, 0x005, 0x00A, 0x00F, 0x014, 0x011, 0x01E, 0x01B, 0x028, 0x02D, 0x022, 0x027, 0x03C, 0x039, 0x036, 0x033 }, { 0x000, 0x006, 0x00C, 0x00A, 0x018, 0x01E, 0x014, 0x012, 0x030, 0x036, 0x03C, 0x03A, 0x028, 0x02E, 0x024, 0x022 }, { 0x000, 0x007, 0x00E, 0x009, 0x01C, 0x01B, 0x012, 0x015, 0x038, 0x03F, 0x036, 0x031, 0x024, 0x023, 0x02A, 0x02D }, { 0x000, 0x008, 0x010, 0x018, 0x020, 0x028, 0x030, 0x038, 0x040, 0x048, 0x050, 0x058, 0x060, 0x068, 0x070, 0x078 }, { 0x000, 0x009, 0x012, 0x01B, 0x024, 0x02D, 0x036, 0x03F, 0x048, 0x041, 0x05A, 0x053, 0x06C, 0x065, 0x07E, 0x077 }, { 0x000, 0x00A, 0x014, 0x01E, 0x028, 0x022, 0x03C, 0x036, 0x050, 0x05A, 0x044, 0x04E, 0x078, 0x072, 0x06C, 0x066 }, { 0x000, 0x00B, 0x016, 0x01D, 0x02C, 0x027, 0x03A, 0x031, 0x058, 0x053, 0x04E, 0x045, 0x074, 0x07F, 0x062, 0x069 }, { 0x000, 0x00C, 0x018, 0x014, 0x030, 0x03C, 0x028, 0x024, 0x060, 0x06C, 0x078, 0x074, 0x050, 0x05C, 0x048, 0x044 }, { 0x000, 0x00D, 0x01A, 0x017, 0x034, 0x039, 0x02E, 0x023, 0x068, 0x065, 0x072, 0x07F, 0x05C, 0x051, 0x046, 0x04B }, { 0x000, 0x00E, 0x01C, 0x012, 0x038, 0x036, 0x024, 0x02A, 0x070, 0x07E, 0x06C, 0x062, 0x048, 0x046, 0x054, 0x05A }, { 0x000, 0x00F, 0x01E, 0x011, 0x03C, 0x033, 0x022, 0x02D, 0x078, 0x077, 0x066, 0x069, 0x044, 0x04B, 0x05A, 0x055 }, { 0x000, 0x010, 0x020, 0x030, 0x040, 0x050, 0x060, 0x070, 0x080, 0x090, 0x0A0, 0x0B0, 0x0C0, 0x0D0, 0x0E0, 0x0F0 }, { 0x000, 0x011, 0x022, 0x033, 0x044, 0x055, 0x066, 0x077, 0x088, 0x099, 0x0AA, 0x0BB, 0x0CC, 0x0DD, 0x0EE, 0x0FF }, { 0x000, 0x012, 0x024, 0x036, 0x048, 0x05A, 0x06C, 0x07E, 0x090, 0x082, 0x0B4, 0x0A6, 0x0D8, 0x0CA, 0x0FC, 0x0EE }, { 0x000, 0x013, 0x026, 0x035, 0x04C, 0x05F, 0x06A, 0x079, 0x098, 0x08B, 0x0BE, 0x0AD, 0x0D4, 0x0C7, 0x0F2, 0x0E1 }, { 0x000, 0x014, 0x028, 0x03C, 0x050, 0x044, 0x078, 0x06C, 0x0A0, 0x0B4, 0x088, 0x09C, 0x0F0, 0x0E4, 0x0D8, 0x0CC }, { 0x000, 0x015, 0x02A, 0x03F, 0x054, 0x041, 0x07E, 0x06B, 0x0A8, 0x0BD, 0x082, 0x097, 0x0FC, 0x0E9, 0x0D6, 0x0C3 }, { 0x000, 0x016, 0x02C, 0x03A, 0x058, 0x04E, 0x074, 0x062, 0x0B0, 0x0A6, 0x09C, 0x08A, 0x0E8, 0x0FE, 0x0C4, 0x0D2 }, { 0x000, 0x017, 0x02E, 0x039, 0x05C, 0x04B, 0x072, 0x065, 0x0B8, 0x0AF, 0x096, 0x081, 0x0E4, 0x0F3, 0x0CA, 0x0DD }, { 0x000, 0x018, 0x030, 0x028, 0x060, 0x078, 0x050, 0x048, 0x0C0, 0x0D8, 0x0F0, 0x0E8, 0x0A0, 0x0B8, 0x090, 0x088 }, { 0x000, 0x019, 0x032, 0x02B, 0x064, 0x07D, 0x056, 0x04F, 0x0C8, 0x0D1, 0x0FA, 0x0E3, 0x0AC, 0x0B5, 0x09E, 0x087 }, { 0x000, 0x01A, 0x034, 0x02E, 0x068, 0x072, 0x05C, 0x046, 0x0D0, 0x0CA, 0x0E4, 0x0FE, 0x0B8, 0x0A2, 0x08C, 0x096 }, { 0x000, 0x01B, 0x036, 0x02D, 0x06C, 0x077, 0x05A, 0x041, 0x0D8, 0x0C3, 0x0EE, 0x0F5, 0x0B4, 0x0AF, 0x082, 0x099 }, { 0x000, 0x01C, 0x038, 0x024, 0x070, 0x06C, 0x048, 0x054, 0x0E0, 0x0FC, 0x0D8, 0x0C4, 0x090, 0x08C, 0x0A8, 0x0B4 }, { 0x000, 0x01D, 0x03A, 0x027, 0x074, 0x069, 0x04E, 0x053, 0x0E8, 0x0F5, 0x0D2, 0x0CF, 0x09C, 0x081, 0x0A6, 0x0BB }, { 0x000, 0x01E, 0x03C, 0x022, 0x078, 0x066, 0x044, 0x05A, 0x0F0, 0x0EE, 0x0CC, 0x0D2, 0x088, 0x096, 0x0B4, 0x0AA }, { 0x000, 0x01F, 0x03E, 0x021, 0x07C, 0x063, 0x042, 0x05D, 0x0F8, 0x0E7, 0x0C6, 0x0D9, 0x084, 0x09B, 0x0BA, 0x0A5 }, { 0x000, 0x020, 0x040, 0x060, 0x080, 0x0A0, 0x0C0, 0x0E0, 0x100, 0x120, 0x140, 0x160, 0x180, 0x1A0, 0x1C0, 0x1E0 }, { 0x000, 0x021, 0x042, 0x063, 0x084, 0x0A5, 0x0C6, 0x0E7, 0x108, 0x129, 0x14A, 0x16B, 0x18C, 0x1AD, 0x1CE, 0x1EF }, { 0x000, 0x022, 0x044, 0x066, 0x088, 0x0AA, 0x0CC, 0x0EE, 0x110, 0x132, 0x154, 0x176, 0x198, 0x1BA, 0x1DC, 0x1FE }, { 0x000, 0x023, 0x046, 0x065, 0x08C, 0x0AF, 0x0CA, 0x0E9, 0x118, 0x13B, 0x15E, 0x17D, 0x194, 0x1B7, 0x1D2, 0x1F1 }, { 0x000, 0x024, 0x048, 0x06C, 0x090, 0x0B4, 0x0D8, 0x0FC, 0x120, 0x104, 0x168, 0x14C, 0x1B0, 0x194, 0x1F8, 0x1DC }, { 0x000, 0x025, 0x04A, 0x06F, 0x094, 0x0B1, 0x0DE, 0x0FB, 0x128, 0x10D, 0x162, 0x147, 0x1BC, 0x199, 0x1F6, 0x1D3 }, { 0x000, 0x026, 0x04C, 0x06A, 0x098, 0x0BE, 0x0D4, 0x0F2, 0x130, 0x116, 0x17C, 0x15A, 0x1A8, 0x18E, 0x1E4, 0x1C2 }, { 0x000, 0x027, 0x04E, 0x069, 0x09C, 0x0BB, 0x0D2, 0x0F5, 0x138, 0x11F, 0x176, 0x151, 0x1A4, 0x183, 0x1EA, 0x1CD }, { 0x000, 0x028, 0x050, 0x078, 0x0A0, 0x088, 0x0F0, 0x0D8, 0x140, 0x168, 0x110, 0x138, 0x1E0, 0x1C8, 0x1B0, 0x198 }, { 0x000, 0x029, 0x052, 0x07B, 0x0A4, 0x08D, 0x0F6, 0x0DF, 0x148, 0x161, 0x11A, 0x133, 0x1EC, 0x1C5, 0x1BE, 0x197 }, { 0x000, 0x02A, 0x054, 0x07E, 0x0A8, 0x082, 0x0FC, 0x0D6, 0x150, 0x17A, 0x104, 0x12E, 0x1F8, 0x1D2, 0x1AC, 0x186 }, { 0x000, 0x02B, 0x056, 0x07D, 0x0AC, 0x087, 0x0FA, 0x0D1, 0x158, 0x173, 0x10E, 0x125, 0x1F4, 0x1DF, 0x1A2, 0x189 }, { 0x000, 0x02C, 0x058, 0x074, 0x0B0, 0x09C, 0x0E8, 0x0C4, 0x160, 0x14C, 0x138, 0x114, 0x1D0, 0x1FC, 0x188, 0x1A4 }, { 0x000, 0x02D, 0x05A, 0x077, 0x0B4, 0x099, 0x0EE, 0x0C3, 0x168, 0x145, 0x132, 0x11F, 0x1DC, 0x1F1, 0x186, 0x1AB }, { 0x000, 0x02E, 0x05C, 0x072, 0x0B8, 0x096, 0x0E4, 0x0CA, 0x170, 0x15E, 0x12C, 0x102, 0x1C8, 0x1E6, 0x194, 0x1BA }, { 0x000, 0x02F, 0x05E, 0x071, 0x0BC, 0x093, 0x0E2, 0x0CD, 0x178, 0x157, 0x126, 0x109, 0x1C4, 0x1EB, 0x19A, 0x1B5 }, { 0x000, 0x030, 0x060, 0x050, 0x0C0, 0x0F0, 0x0A0, 0x090, 0x180, 0x1B0, 0x1E0, 0x1D0, 0x140, 0x170, 0x120, 0x110 }, { 0x000, 0x031, 0x062, 0x053, 0x0C4, 0x0F5, 0x0A6, 0x097, 0x188, 0x1B9, 0x1EA, 0x1DB, 0x14C, 0x17D, 0x12E, 0x11F }, { 0x000, 0x032, 0x064, 0x056, 0x0C8, 0x0FA, 0x0AC, 0x09E, 0x190, 0x1A2, 0x1F4, 0x1C6, 0x158, 0x16A, 0x13C, 0x10E }, { 0x000, 0x033, 0x066, 0x055, 0x0CC, 0x0FF, 0x0AA, 0x099, 0x198, 0x1AB, 0x1FE, 0x1CD, 0x154, 0x167, 0x132, 0x101 }, { 0x000, 0x034, 0x068, 0x05C, 0x0D0, 0x0E4, 0x0B8, 0x08C, 0x1A0, 0x194, 0x1C8, 0x1FC, 0x170, 0x144, 0x118, 0x12C }, { 0x000, 0x035, 0x06A, 0x05F, 0x0D4, 0x0E1, 0x0BE, 0x08B, 0x1A8, 0x19D, 0x1C2, 0x1F7, 0x17C, 0x149, 0x116, 0x123 }, { 0x000, 0x036, 0x06C, 0x05A, 0x0D8, 0x0EE, 0x0B4, 0x082, 0x1B0, 0x186, 0x1DC, 0x1EA, 0x168, 0x15E, 0x104, 0x132 }, { 0x000, 0x037, 0x06E, 0x059, 0x0DC, 0x0EB, 0x0B2, 0x085, 0x1B8, 0x18F, 0x1D6, 0x1E1, 0x164, 0x153, 0x10A, 0x13D }, { 0x000, 0x038, 0x070, 0x048, 0x0E0, 0x0D8, 0x090, 0x0A8, 0x1C0, 0x1F8, 0x1B0, 0x188, 0x120, 0x118, 0x150, 0x168 }, { 0x000, 0x039, 0x072, 0x04B, 0x0E4, 0x0DD, 0x096, 0x0AF, 0x1C8, 0x1F1, 0x1BA, 0x183, 0x12C, 0x115, 0x15E, 0x167 }, { 0x000, 0x03A, 0x074, 0x04E, 0x0E8, 0x0D2, 0x09C, 0x0A6, 0x1D0, 0x1EA, 0x1A4, 0x19E, 0x138, 0x102, 0x14C, 0x176 }, { 0x000, 0x03B, 0x076, 0x04D, 0x0EC, 0x0D7, 0x09A, 0x0A1, 0x1D8, 0x1E3, 0x1AE, 0x195, 0x134, 0x10F, 0x142, 0x179 }, { 0x000, 0x03C, 0x078, 0x044, 0x0F0, 0x0CC, 0x088, 0x0B4, 0x1E0, 0x1DC, 0x198, 0x1A4, 0x110, 0x12C, 0x168, 0x154 }, { 0x000, 0x03D, 0x07A, 0x047, 0x0F4, 0x0C9, 0x08E, 0x0B3, 0x1E8, 0x1D5, 0x192, 0x1AF, 0x11C, 0x121, 0x166, 0x15B }, { 0x000, 0x03E, 0x07C, 0x042, 0x0F8, 0x0C6, 0x084, 0x0BA, 0x1F0, 0x1CE, 0x18C, 0x1B2, 0x108, 0x136, 0x174, 0x14A }, { 0x000, 0x03F, 0x07E, 0x041, 0x0FC, 0x0C3, 0x082, 0x0BD, 0x1F8, 0x1C7, 0x186, 0x1B9, 0x104, 0x13B, 0x17A, 0x145 }, { 0x000, 0x040, 0x080, 0x0C0, 0x100, 0x140, 0x180, 0x1C0, 0x200, 0x240, 0x280, 0x2C0, 0x300, 0x340, 0x380, 0x3C0 }, { 0x000, 0x041, 0x082, 0x0C3, 0x104, 0x145, 0x186, 0x1C7, 0x208, 0x249, 0x28A, 0x2CB, 0x30C, 0x34D, 0x38E, 0x3CF }, { 0x000, 0x042, 0x084, 0x0C6, 0x108, 0x14A, 0x18C, 0x1CE, 0x210, 0x252, 0x294, 0x2D6, 0x318, 0x35A, 0x39C, 0x3DE }, { 0x000, 0x043, 0x086, 0x0C5, 0x10C, 0x14F, 0x18A, 0x1C9, 0x218, 0x25B, 0x29E, 0x2DD, 0x314, 0x357, 0x392, 0x3D1 }, { 0x000, 0x044, 0x088, 0x0CC, 0x110, 0x154, 0x198, 0x1DC, 0x220, 0x264, 0x2A8, 0x2EC, 0x330, 0x374, 0x3B8, 0x3FC }, { 0x000, 0x045, 0x08A, 0x0CF, 0x114, 0x151, 0x19E, 0x1DB, 0x228, 0x26D, 0x2A2, 0x2E7, 0x33C, 0x379, 0x3B6, 0x3F3 }, { 0x000, 0x046, 0x08C, 0x0CA, 0x118, 0x15E, 0x194, 0x1D2, 0x230, 0x276, 0x2BC, 0x2FA, 0x328, 0x36E, 0x3A4, 0x3E2 }, { 0x000, 0x047, 0x08E, 0x0C9, 0x11C, 0x15B, 0x192, 0x1D5, 0x238, 0x27F, 0x2B6, 0x2F1, 0x324, 0x363, 0x3AA, 0x3ED }, { 0x000, 0x048, 0x090, 0x0D8, 0x120, 0x168, 0x1B0, 0x1F8, 0x240, 0x208, 0x2D0, 0x298, 0x360, 0x328, 0x3F0, 0x3B8 }, { 0x000, 0x049, 0x092, 0x0DB, 0x124, 0x16D, 0x1B6, 0x1FF, 0x248, 0x201, 0x2DA, 0x293, 0x36C, 0x325, 0x3FE, 0x3B7 }, { 0x000, 0x04A, 0x094, 0x0DE, 0x128, 0x162, 0x1BC, 0x1F6, 0x250, 0x21A, 0x2C4, 0x28E, 0x378, 0x332, 0x3EC, 0x3A6 }, { 0x000, 0x04B, 0x096, 0x0DD, 0x12C, 0x167, 0x1BA, 0x1F1, 0x258, 0x213, 0x2CE, 0x285, 0x374, 0x33F, 0x3E2, 0x3A9 }, { 0x000, 0x04C, 0x098, 0x0D4, 0x130, 0x17C, 0x1A8, 0x1E4, 0x260, 0x22C, 0x2F8, 0x2B4, 0x350, 0x31C, 0x3C8, 0x384 }, { 0x000, 0x04D, 0x09A, 0x0D7, 0x134, 0x179, 0x1AE, 0x1E3, 0x268, 0x225, 0x2F2, 0x2BF, 0x35C, 0x311, 0x3C6, 0x38B }, { 0x000, 0x04E, 0x09C, 0x0D2, 0x138, 0x176, 0x1A4, 0x1EA, 0x270, 0x23E, 0x2EC, 0x2A2, 0x348, 0x306, 0x3D4, 0x39A }, { 0x000, 0x04F, 0x09E, 0x0D1, 0x13C, 0x173, 0x1A2, 0x1ED, 0x278, 0x237, 0x2E6, 0x2A9, 0x344, 0x30B, 0x3DA, 0x395 }, { 0x000, 0x050, 0x0A0, 0x0F0, 0x140, 0x110, 0x1E0, 0x1B0, 0x280, 0x2D0, 0x220, 0x270, 0x3C0, 0x390, 0x360, 0x330 }, { 0x000, 0x051, 0x0A2, 0x0F3, 0x144, 0x115, 0x1E6, 0x1B7, 0x288, 0x2D9, 0x22A, 0x27B, 0x3CC, 0x39D, 0x36E, 0x33F }, { 0x000, 0x052, 0x0A4, 0x0F6, 0x148, 0x11A, 0x1EC, 0x1BE, 0x290, 0x2C2, 0x234, 0x266, 0x3D8, 0x38A, 0x37C, 0x32E }, { 0x000, 0x053, 0x0A6, 0x0F5, 0x14C, 0x11F, 0x1EA, 0x1B9, 0x298, 0x2CB, 0x23E, 0x26D, 0x3D4, 0x387, 0x372, 0x321 }, { 0x000, 0x054, 0x0A8, 0x0FC, 0x150, 0x104, 0x1F8, 0x1AC, 0x2A0, 0x2F4, 0x208, 0x25C, 0x3F0, 0x3A4, 0x358, 0x30C }, { 0x000, 0x055, 0x0AA, 0x0FF, 0x154, 0x101, 0x1FE, 0x1AB, 0x2A8, 0x2FD, 0x202, 0x257, 0x3FC, 0x3A9, 0x356, 0x303 }, { 0x000, 0x056, 0x0AC, 0x0FA, 0x158, 0x10E, 0x1F4, 0x1A2, 0x2B0, 0x2E6, 0x21C, 0x24A, 0x3E8, 0x3BE, 0x344, 0x312 }, { 0x000, 0x057, 0x0AE, 0x0F9, 0x15C, 0x10B, 0x1F2, 0x1A5, 0x2B8, 0x2EF, 0x216, 0x241, 0x3E4, 0x3B3, 0x34A, 0x31D }, { 0x000, 0x058, 0x0B0, 0x0E8, 0x160, 0x138, 0x1D0, 0x188, 0x2C0, 0x298, 0x270, 0x228, 0x3A0, 0x3F8, 0x310, 0x348 }, { 0x000, 0x059, 0x0B2, 0x0EB, 0x164, 0x13D, 0x1D6, 0x18F, 0x2C8, 0x291, 0x27A, 0x223, 0x3AC, 0x3F5, 0x31E, 0x347 }, { 0x000, 0x05A, 0x0B4, 0x0EE, 0x168, 0x132, 0x1DC, 0x186, 0x2D0, 0x28A, 0x264, 0x23E, 0x3B8, 0x3E2, 0x30C, 0x356 }, { 0x000, 0x05B, 0x0B6, 0x0ED, 0x16C, 0x137, 0x1DA, 0x181, 0x2D8, 0x283, 0x26E, 0x235, 0x3B4, 0x3EF, 0x302, 0x359 }, { 0x000, 0x05C, 0x0B8, 0x0E4, 0x170, 0x12C, 0x1C8, 0x194, 0x2E0, 0x2BC, 0x258, 0x204, 0x390, 0x3CC, 0x328, 0x374 }, { 0x000, 0x05D, 0x0BA, 0x0E7, 0x174, 0x129, 0x1CE, 0x193, 0x2E8, 0x2B5, 0x252, 0x20F, 0x39C, 0x3C1, 0x326, 0x37B }, { 0x000, 0x05E, 0x0BC, 0x0E2, 0x178, 0x126, 0x1C4, 0x19A, 0x2F0, 0x2AE, 0x24C, 0x212, 0x388, 0x3D6, 0x334, 0x36A }, { 0x000, 0x05F, 0x0BE, 0x0E1, 0x17C, 0x123, 0x1C2, 0x19D, 0x2F8, 0x2A7, 0x246, 0x219, 0x384, 0x3DB, 0x33A, 0x365 }, { 0x000, 0x060, 0x0C0, 0x0A0, 0x180, 0x1E0, 0x140, 0x120, 0x300, 0x360, 0x3C0, 0x3A0, 0x280, 0x2E0, 0x240, 0x220 }, { 0x000, 0x061, 0x0C2, 0x0A3, 0x184, 0x1E5, 0x146, 0x127, 0x308, 0x369, 0x3CA, 0x3AB, 0x28C, 0x2ED, 0x24E, 0x22F }, { 0x000, 0x062, 0x0C4, 0x0A6, 0x188, 0x1EA, 0x14C, 0x12E, 0x310, 0x372, 0x3D4, 0x3B6, 0x298, 0x2FA, 0x25C, 0x23E }, { 0x000, 0x063, 0x0C6, 0x0A5, 0x18C, 0x1EF, 0x14A, 0x129, 0x318, 0x37B, 0x3DE, 0x3BD, 0x294, 0x2F7, 0x252, 0x231 }, { 0x000, 0x064, 0x0C8, 0x0AC, 0x190, 0x1F4, 0x158, 0x13C, 0x320, 0x344, 0x3E8, 0x38C, 0x2B0, 0x2D4, 0x278, 0x21C }, { 0x000, 0x065, 0x0CA, 0x0AF, 0x194, 0x1F1, 0x15E, 0x13B, 0x328, 0x34D, 0x3E2, 0x387, 0x2BC, 0x2D9, 0x276, 0x213 }, { 0x000, 0x066, 0x0CC, 0x0AA, 0x198, 0x1FE, 0x154, 0x132, 0x330, 0x356, 0x3FC, 0x39A, 0x2A8, 0x2CE, 0x264, 0x202 }, { 0x000, 0x067, 0x0CE, 0x0A9, 0x19C, 0x1FB, 0x152, 0x135, 0x338, 0x35F, 0x3F6, 0x391, 0x2A4, 0x2C3, 0x26A, 0x20D }, { 0x000, 0x068, 0x0D0, 0x0B8, 0x1A0, 0x1C8, 0x170, 0x118, 0x340, 0x328, 0x390, 0x3F8, 0x2E0, 0x288, 0x230, 0x258 }, { 0x000, 0x069, 0x0D2, 0x0BB, 0x1A4, 0x1CD, 0x176, 0x11F, 0x348, 0x321, 0x39A, 0x3F3, 0x2EC, 0x285, 0x23E, 0x257 }, { 0x000, 0x06A, 0x0D4, 0x0BE, 0x1A8, 0x1C2, 0x17C, 0x116, 0x350, 0x33A, 0x384, 0x3EE, 0x2F8, 0x292, 0x22C, 0x246 }, { 0x000, 0x06B, 0x0D6, 0x0BD, 0x1AC, 0x1C7, 0x17A, 0x111, 0x358, 0x333, 0x38E, 0x3E5, 0x2F4, 0x29F, 0x222, 0x249 }, { 0x000, 0x06C, 0x0D8, 0x0B4, 0x1B0, 0x1DC, 0x168, 0x104, 0x360, 0x30C, 0x3B8, 0x3D4, 0x2D0, 0x2BC, 0x208, 0x264 }, { 0x000, 0x06D, 0x0DA, 0x0B7, 0x1B4, 0x1D9, 0x16E, 0x103, 0x368, 0x305, 0x3B2, 0x3DF, 0x2DC, 0x2B1, 0x206, 0x26B }, { 0x000, 0x06E, 0x0DC, 0x0B2, 0x1B8, 0x1D6, 0x164, 0x10A, 0x370, 0x31E, 0x3AC, 0x3C2, 0x2C8, 0x2A6, 0x214, 0x27A }, { 0x000, 0x06F, 0x0DE, 0x0B1, 0x1BC, 0x1D3, 0x162, 0x10D, 0x378, 0x317, 0x3A6, 0x3C9, 0x2C4, 0x2AB, 0x21A, 0x275 }, { 0x000, 0x070, 0x0E0, 0x090, 0x1C0, 0x1B0, 0x120, 0x150, 0x380, 0x3F0, 0x360, 0x310, 0x240, 0x230, 0x2A0, 0x2D0 }, { 0x000, 0x071, 0x0E2, 0x093, 0x1C4, 0x1B5, 0x126, 0x157, 0x388, 0x3F9, 0x36A, 0x31B, 0x24C, 0x23D, 0x2AE, 0x2DF }, { 0x000, 0x072, 0x0E4, 0x096, 0x1C8, 0x1BA, 0x12C, 0x15E, 0x390, 0x3E2, 0x374, 0x306, 0x258, 0x22A, 0x2BC, 0x2CE }, { 0x000, 0x073, 0x0E6, 0x095, 0x1CC, 0x1BF, 0x12A, 0x159, 0x398, 0x3EB, 0x37E, 0x30D, 0x254, 0x227, 0x2B2, 0x2C1 }, { 0x000, 0x074, 0x0E8, 0x09C, 0x1D0, 0x1A4, 0x138, 0x14C, 0x3A0, 0x3D4, 0x348, 0x33C, 0x270, 0x204, 0x298, 0x2EC }, { 0x000, 0x075, 0x0EA, 0x09F, 0x1D4, 0x1A1, 0x13E, 0x14B, 0x3A8, 0x3DD, 0x342, 0x337, 0x27C, 0x209, 0x296, 0x2E3 }, { 0x000, 0x076, 0x0EC, 0x09A, 0x1D8, 0x1AE, 0x134, 0x142, 0x3B0, 0x3C6, 0x35C, 0x32A, 0x268, 0x21E, 0x284, 0x2F2 }, { 0x000, 0x077, 0x0EE, 0x099, 0x1DC, 0x1AB, 0x132, 0x145, 0x3B8, 0x3CF, 0x356, 0x321, 0x264, 0x213, 0x28A, 0x2FD }, { 0x000, 0x078, 0x0F0, 0x088, 0x1E0, 0x198, 0x110, 0x168, 0x3C0, 0x3B8, 0x330, 0x348, 0x220, 0x258, 0x2D0, 0x2A8 }, { 0x000, 0x079, 0x0F2, 0x08B, 0x1E4, 0x19D, 0x116, 0x16F, 0x3C8, 0x3B1, 0x33A, 0x343, 0x22C, 0x255, 0x2DE, 0x2A7 }, { 0x000, 0x07A, 0x0F4, 0x08E, 0x1E8, 0x192, 0x11C, 0x166, 0x3D0, 0x3AA, 0x324, 0x35E, 0x238, 0x242, 0x2CC, 0x2B6 }, { 0x000, 0x07B, 0x0F6, 0x08D, 0x1EC, 0x197, 0x11A, 0x161, 0x3D8, 0x3A3, 0x32E, 0x355, 0x234, 0x24F, 0x2C2, 0x2B9 }, { 0x000, 0x07C, 0x0F8, 0x084, 0x1F0, 0x18C, 0x108, 0x174, 0x3E0, 0x39C, 0x318, 0x364, 0x210, 0x26C, 0x2E8, 0x294 }, { 0x000, 0x07D, 0x0FA, 0x087, 0x1F4, 0x189, 0x10E, 0x173, 0x3E8, 0x395, 0x312, 0x36F, 0x21C, 0x261, 0x2E6, 0x29B }, { 0x000, 0x07E, 0x0FC, 0x082, 0x1F8, 0x186, 0x104, 0x17A, 0x3F0, 0x38E, 0x30C, 0x372, 0x208, 0x276, 0x2F4, 0x28A }, { 0x000, 0x07F, 0x0FE, 0x081, 0x1FC, 0x183, 0x102, 0x17D, 0x3F8, 0x387, 0x306, 0x379, 0x204, 0x27B, 0x2FA, 0x285 }, { 0x000, 0x080, 0x100, 0x180, 0x200, 0x280, 0x300, 0x380, 0x400, 0x480, 0x500, 0x580, 0x600, 0x680, 0x700, 0x780 }, { 0x000, 0x081, 0x102, 0x183, 0x204, 0x285, 0x306, 0x387, 0x408, 0x489, 0x50A, 0x58B, 0x60C, 0x68D, 0x70E, 0x78F }, { 0x000, 0x082, 0x104, 0x186, 0x208, 0x28A, 0x30C, 0x38E, 0x410, 0x492, 0x514, 0x596, 0x618, 0x69A, 0x71C, 0x79E }, { 0x000, 0x083, 0x106, 0x185, 0x20C, 0x28F, 0x30A, 0x389, 0x418, 0x49B, 0x51E, 0x59D, 0x614, 0x697, 0x712, 0x791 }, { 0x000, 0x084, 0x108, 0x18C, 0x210, 0x294, 0x318, 0x39C, 0x420, 0x4A4, 0x528, 0x5AC, 0x630, 0x6B4, 0x738, 0x7BC }, { 0x000, 0x085, 0x10A, 0x18F, 0x214, 0x291, 0x31E, 0x39B, 0x428, 0x4AD, 0x522, 0x5A7, 0x63C, 0x6B9, 0x736, 0x7B3 }, { 0x000, 0x086, 0x10C, 0x18A, 0x218, 0x29E, 0x314, 0x392, 0x430, 0x4B6, 0x53C, 0x5BA, 0x628, 0x6AE, 0x724, 0x7A2 }, { 0x000, 0x087, 0x10E, 0x189, 0x21C, 0x29B, 0x312, 0x395, 0x438, 0x4BF, 0x536, 0x5B1, 0x624, 0x6A3, 0x72A, 0x7AD }, { 0x000, 0x088, 0x110, 0x198, 0x220, 0x2A8, 0x330, 0x3B8, 0x440, 0x4C8, 0x550, 0x5D8, 0x660, 0x6E8, 0x770, 0x7F8 }, { 0x000, 0x089, 0x112, 0x19B, 0x224, 0x2AD, 0x336, 0x3BF, 0x448, 0x4C1, 0x55A, 0x5D3, 0x66C, 0x6E5, 0x77E, 0x7F7 }, { 0x000, 0x08A, 0x114, 0x19E, 0x228, 0x2A2, 0x33C, 0x3B6, 0x450, 0x4DA, 0x544, 0x5CE, 0x678, 0x6F2, 0x76C, 0x7E6 }, { 0x000, 0x08B, 0x116, 0x19D, 0x22C, 0x2A7, 0x33A, 0x3B1, 0x458, 0x4D3, 0x54E, 0x5C5, 0x674, 0x6FF, 0x762, 0x7E9 }, { 0x000, 0x08C, 0x118, 0x194, 0x230, 0x2BC, 0x328, 0x3A4, 0x460, 0x4EC, 0x578, 0x5F4, 0x650, 0x6DC, 0x748, 0x7C4 }, { 0x000, 0x08D, 0x11A, 0x197, 0x234, 0x2B9, 0x32E, 0x3A3, 0x468, 0x4E5, 0x572, 0x5FF, 0x65C, 0x6D1, 0x746, 0x7CB }, { 0x000, 0x08E, 0x11C, 0x192, 0x238, 0x2B6, 0x324, 0x3AA, 0x470, 0x4FE, 0x56C, 0x5E2, 0x648, 0x6C6, 0x754, 0x7DA }, { 0x000, 0x08F, 0x11E, 0x191, 0x23C, 0x2B3, 0x322, 0x3AD, 0x478, 0x4F7, 0x566, 0x5E9, 0x644, 0x6CB, 0x75A, 0x7D5 }, { 0x000, 0x090, 0x120, 0x1B0, 0x240, 0x2D0, 0x360, 0x3F0, 0x480, 0x410, 0x5A0, 0x530, 0x6C0, 0x650, 0x7E0, 0x770 }, { 0x000, 0x091, 0x122, 0x1B3, 0x244, 0x2D5, 0x366, 0x3F7, 0x488, 0x419, 0x5AA, 0x53B, 0x6CC, 0x65D, 0x7EE, 0x77F }, { 0x000, 0x092, 0x124, 0x1B6, 0x248, 0x2DA, 0x36C, 0x3FE, 0x490, 0x402, 0x5B4, 0x526, 0x6D8, 0x64A, 0x7FC, 0x76E }, { 0x000, 0x093, 0x126, 0x1B5, 0x24C, 0x2DF, 0x36A, 0x3F9, 0x498, 0x40B, 0x5BE, 0x52D, 0x6D4, 0x647, 0x7F2, 0x761 }, { 0x000, 0x094, 0x128, 0x1BC, 0x250, 0x2C4, 0x378, 0x3EC, 0x4A0, 0x434, 0x588, 0x51C, 0x6F0, 0x664, 0x7D8, 0x74C }, { 0x000, 0x095, 0x12A, 0x1BF, 0x254, 0x2C1, 0x37E, 0x3EB, 0x4A8, 0x43D, 0x582, 0x517, 0x6FC, 0x669, 0x7D6, 0x743 }, { 0x000, 0x096, 0x12C, 0x1BA, 0x258, 0x2CE, 0x374, 0x3E2, 0x4B0, 0x426, 0x59C, 0x50A, 0x6E8, 0x67E, 0x7C4, 0x752 }, { 0x000, 0x097, 0x12E, 0x1B9, 0x25C, 0x2CB, 0x372, 0x3E5, 0x4B8, 0x42F, 0x596, 0x501, 0x6E4, 0x673, 0x7CA, 0x75D }, { 0x000, 0x098, 0x130, 0x1A8, 0x260, 0x2F8, 0x350, 0x3C8, 0x4C0, 0x458, 0x5F0, 0x568, 0x6A0, 0x638, 0x790, 0x708 }, { 0x000, 0x099, 0x132, 0x1AB, 0x264, 0x2FD, 0x356, 0x3CF, 0x4C8, 0x451, 0x5FA, 0x563, 0x6AC, 0x635, 0x79E, 0x707 }, { 0x000, 0x09A, 0x134, 0x1AE, 0x268, 0x2F2, 0x35C, 0x3C6, 0x4D0, 0x44A, 0x5E4, 0x57E, 0x6B8, 0x622, 0x78C, 0x716 }, { 0x000, 0x09B, 0x136, 0x1AD, 0x26C, 0x2F7, 0x35A, 0x3C1, 0x4D8, 0x443, 0x5EE, 0x575, 0x6B4, 0x62F, 0x782, 0x719 }, { 0x000, 0x09C, 0x138, 0x1A4, 0x270, 0x2EC, 0x348, 0x3D4, 0x4E0, 0x47C, 0x5D8, 0x544, 0x690, 0x60C, 0x7A8, 0x734 }, { 0x000, 0x09D, 0x13A, 0x1A7, 0x274, 0x2E9, 0x34E, 0x3D3, 0x4E8, 0x475, 0x5D2, 0x54F, 0x69C, 0x601, 0x7A6, 0x73B }, { 0x000, 0x09E, 0x13C, 0x1A2, 0x278, 0x2E6, 0x344, 0x3DA, 0x4F0, 0x46E, 0x5CC, 0x552, 0x688, 0x616, 0x7B4, 0x72A }, { 0x000, 0x09F, 0x13E, 0x1A1, 0x27C, 0x2E3, 0x342, 0x3DD, 0x4F8, 0x467, 0x5C6, 0x559, 0x684, 0x61B, 0x7BA, 0x725 }, { 0x000, 0x0A0, 0x140, 0x1E0, 0x280, 0x220, 0x3C0, 0x360, 0x500, 0x5A0, 0x440, 0x4E0, 0x780, 0x720, 0x6C0, 0x660 }, { 0x000, 0x0A1, 0x142, 0x1E3, 0x284, 0x225, 0x3C6, 0x367, 0x508, 0x5A9, 0x44A, 0x4EB, 0x78C, 0x72D, 0x6CE, 0x66F }, { 0x000, 0x0A2, 0x144, 0x1E6, 0x288, 0x22A, 0x3CC, 0x36E, 0x510, 0x5B2, 0x454, 0x4F6, 0x798, 0x73A, 0x6DC, 0x67E }, { 0x000, 0x0A3, 0x146, 0x1E5, 0x28C, 0x22F, 0x3CA, 0x369, 0x518, 0x5BB, 0x45E, 0x4FD, 0x794, 0x737, 0x6D2, 0x671 }, { 0x000, 0x0A4, 0x148, 0x1EC, 0x290, 0x234, 0x3D8, 0x37C, 0x520, 0x584, 0x468, 0x4CC, 0x7B0, 0x714, 0x6F8, 0x65C }, { 0x000, 0x0A5, 0x14A, 0x1EF, 0x294, 0x231, 0x3DE, 0x37B, 0x528, 0x58D, 0x462, 0x4C7, 0x7BC, 0x719, 0x6F6, 0x653 }, { 0x000, 0x0A6, 0x14C, 0x1EA, 0x298, 0x23E, 0x3D4, 0x372, 0x530, 0x596, 0x47C, 0x4DA, 0x7A8, 0x70E, 0x6E4, 0x642 }, { 0x000, 0x0A7, 0x14E, 0x1E9, 0x29C, 0x23B, 0x3D2, 0x375, 0x538, 0x59F, 0x476, 0x4D1, 0x7A4, 0x703, 0x6EA, 0x64D }, { 0x000, 0x0A8, 0x150, 0x1F8, 0x2A0, 0x208, 0x3F0, 0x358, 0x540, 0x5E8, 0x410, 0x4B8, 0x7E0, 0x748, 0x6B0, 0x618 }, { 0x000, 0x0A9, 0x152, 0x1FB, 0x2A4, 0x20D, 0x3F6, 0x35F, 0x548, 0x5E1, 0x41A, 0x4B3, 0x7EC, 0x745, 0x6BE, 0x617 }, { 0x000, 0x0AA, 0x154, 0x1FE, 0x2A8, 0x202, 0x3FC, 0x356, 0x550, 0x5FA, 0x404, 0x4AE, 0x7F8, 0x752, 0x6AC, 0x606 }, { 0x000, 0x0AB, 0x156, 0x1FD, 0x2AC, 0x207, 0x3FA, 0x351, 0x558, 0x5F3, 0x40E, 0x4A5, 0x7F4, 0x75F, 0x6A2, 0x609 }, { 0x000, 0x0AC, 0x158, 0x1F4, 0x2B0, 0x21C, 0x3E8, 0x344, 0x560, 0x5CC, 0x438, 0x494, 0x7D0, 0x77C, 0x688, 0x624 }, { 0x000, 0x0AD, 0x15A, 0x1F7, 0x2B4, 0x219, 0x3EE, 0x343, 0x568, 0x5C5, 0x432, 0x49F, 0x7DC, 0x771, 0x686, 0x62B }, { 0x000, 0x0AE, 0x15C, 0x1F2, 0x2B8, 0x216, 0x3E4, 0x34A, 0x570, 0x5DE, 0x42C, 0x482, 0x7C8, 0x766, 0x694, 0x63A }, { 0x000, 0x0AF, 0x15E, 0x1F1, 0x2BC, 0x213, 0x3E2, 0x34D, 0x578, 0x5D7, 0x426, 0x489, 0x7C4, 0x76B, 0x69A, 0x635 }, { 0x000, 0x0B0, 0x160, 0x1D0, 0x2C0, 0x270, 0x3A0, 0x310, 0x580, 0x530, 0x4E0, 0x450, 0x740, 0x7F0, 0x620, 0x690 }, { 0x000, 0x0B1, 0x162, 0x1D3, 0x2C4, 0x275, 0x3A6, 0x317, 0x588, 0x539, 0x4EA, 0x45B, 0x74C, 0x7FD, 0x62E, 0x69F }, { 0x000, 0x0B2, 0x164, 0x1D6, 0x2C8, 0x27A, 0x3AC, 0x31E, 0x590, 0x522, 0x4F4, 0x446, 0x758, 0x7EA, 0x63C, 0x68E }, { 0x000, 0x0B3, 0x166, 0x1D5, 0x2CC, 0x27F, 0x3AA, 0x319, 0x598, 0x52B, 0x4FE, 0x44D, 0x754, 0x7E7, 0x632, 0x681 }, { 0x000, 0x0B4, 0x168, 0x1DC, 0x2D0, 0x264, 0x3B8, 0x30C, 0x5A0, 0x514, 0x4C8, 0x47C, 0x770, 0x7C4, 0x618, 0x6AC }, { 0x000, 0x0B5, 0x16A, 0x1DF, 0x2D4, 0x261, 0x3BE, 0x30B, 0x5A8, 0x51D, 0x4C2, 0x477, 0x77C, 0x7C9, 0x616, 0x6A3 }, { 0x000, 0x0B6, 0x16C, 0x1DA, 0x2D8, 0x26E, 0x3B4, 0x302, 0x5B0, 0x506, 0x4DC, 0x46A, 0x768, 0x7DE, 0x604, 0x6B2 }, { 0x000, 0x0B7, 0x16E, 0x1D9, 0x2DC, 0x26B, 0x3B2, 0x305, 0x5B8, 0x50F, 0x4D6, 0x461, 0x764, 0x7D3, 0x60A, 0x6BD }, { 0x000, 0x0B8, 0x170, 0x1C8, 0x2E0, 0x258, 0x390, 0x328, 0x5C0, 0x578, 0x4B0, 0x408, 0x720, 0x798, 0x650, 0x6E8 }, { 0x000, 0x0B9, 0x172, 0x1CB, 0x2E4, 0x25D, 0x396, 0x32F, 0x5C8, 0x571, 0x4BA, 0x403, 0x72C, 0x795, 0x65E, 0x6E7 }, { 0x000, 0x0BA, 0x174, 0x1CE, 0x2E8, 0x252, 0x39C, 0x326, 0x5D0, 0x56A, 0x4A4, 0x41E, 0x738, 0x782, 0x64C, 0x6F6 }, { 0x000, 0x0BB, 0x176, 0x1CD, 0x2EC, 0x257, 0x39A, 0x321, 0x5D8, 0x563, 0x4AE, 0x415, 0x734, 0x78F, 0x642, 0x6F9 }, { 0x000, 0x0BC, 0x178, 0x1C4, 0x2F0, 0x24C, 0x388, 0x334, 0x5E0, 0x55C, 0x498, 0x424, 0x710, 0x7AC, 0x668, 0x6D4 }, { 0x000, 0x0BD, 0x17A, 0x1C7, 0x2F4, 0x249, 0x38E, 0x333, 0x5E8, 0x555, 0x492, 0x42F, 0x71C, 0x7A1, 0x666, 0x6DB }, { 0x000, 0x0BE, 0x17C, 0x1C2, 0x2F8, 0x246, 0x384, 0x33A, 0x5F0, 0x54E, 0x48C, 0x432, 0x708, 0x7B6, 0x674, 0x6CA }, { 0x000, 0x0BF, 0x17E, 0x1C1, 0x2FC, 0x243, 0x382, 0x33D, 0x5F8, 0x547, 0x486, 0x439, 0x704, 0x7BB, 0x67A, 0x6C5 }, { 0x000, 0x0C0, 0x180, 0x140, 0x300, 0x3C0, 0x280, 0x240, 0x600, 0x6C0, 0x780, 0x740, 0x500, 0x5C0, 0x480, 0x440 }, { 0x000, 0x0C1, 0x182, 0x143, 0x304, 0x3C5, 0x286, 0x247, 0x608, 0x6C9, 0x78A, 0x74B, 0x50C, 0x5CD, 0x48E, 0x44F }, { 0x000, 0x0C2, 0x184, 0x146, 0x308, 0x3CA, 0x28C, 0x24E, 0x610, 0x6D2, 0x794, 0x756, 0x518, 0x5DA, 0x49C, 0x45E }, { 0x000, 0x0C3, 0x186, 0x145, 0x30C, 0x3CF, 0x28A, 0x249, 0x618, 0x6DB, 0x79E, 0x75D, 0x514, 0x5D7, 0x492, 0x451 }, { 0x000, 0x0C4, 0x188, 0x14C, 0x310, 0x3D4, 0x298, 0x25C, 0x620, 0x6E4, 0x7A8, 0x76C, 0x530, 0x5F4, 0x4B8, 0x47C }, { 0x000, 0x0C5, 0x18A, 0x14F, 0x314, 0x3D1, 0x29E, 0x25B, 0x628, 0x6ED, 0x7A2, 0x767, 0x53C, 0x5F9, 0x4B6, 0x473 }, { 0x000, 0x0C6, 0x18C, 0x14A, 0x318, 0x3DE, 0x294, 0x252, 0x630, 0x6F6, 0x7BC, 0x77A, 0x528, 0x5EE, 0x4A4, 0x462 }, { 0x000, 0x0C7, 0x18E, 0x149, 0x31C, 0x3DB, 0x292, 0x255, 0x638, 0x6FF, 0x7B6, 0x771, 0x524, 0x5E3, 0x4AA, 0x46D }, { 0x000, 0x0C8, 0x190, 0x158, 0x320, 0x3E8, 0x2B0, 0x278, 0x640, 0x688, 0x7D0, 0x718, 0x560, 0x5A8, 0x4F0, 0x438 }, { 0x000, 0x0C9, 0x192, 0x15B, 0x324, 0x3ED, 0x2B6, 0x27F, 0x648, 0x681, 0x7DA, 0x713, 0x56C, 0x5A5, 0x4FE, 0x437 }, { 0x000, 0x0CA, 0x194, 0x15E, 0x328, 0x3E2, 0x2BC, 0x276, 0x650, 0x69A, 0x7C4, 0x70E, 0x578, 0x5B2, 0x4EC, 0x426 }, { 0x000, 0x0CB, 0x196, 0x15D, 0x32C, 0x3E7, 0x2BA, 0x271, 0x658, 0x693, 0x7CE, 0x705, 0x574, 0x5BF, 0x4E2, 0x429 }, { 0x000, 0x0CC, 0x198, 0x154, 0x330, 0x3FC, 0x2A8, 0x264, 0x660, 0x6AC, 0x7F8, 0x734, 0x550, 0x59C, 0x4C8, 0x404 }, { 0x000, 0x0CD, 0x19A, 0x157, 0x334, 0x3F9, 0x2AE, 0x263, 0x668, 0x6A5, 0x7F2, 0x73F, 0x55C, 0x591, 0x4C6, 0x40B }, { 0x000, 0x0CE, 0x19C, 0x152, 0x338, 0x3F6, 0x2A4, 0x26A, 0x670, 0x6BE, 0x7EC, 0x722, 0x548, 0x586, 0x4D4, 0x41A }, { 0x000, 0x0CF, 0x19E, 0x151, 0x33C, 0x3F3, 0x2A2, 0x26D, 0x678, 0x6B7, 0x7E6, 0x729, 0x544, 0x58B, 0x4DA, 0x415 }, { 0x000, 0x0D0, 0x1A0, 0x170, 0x340, 0x390, 0x2E0, 0x230, 0x680, 0x650, 0x720, 0x7F0, 0x5C0, 0x510, 0x460, 0x4B0 }, { 0x000, 0x0D1, 0x1A2, 0x173, 0x344, 0x395, 0x2E6, 0x237, 0x688, 0x659, 0x72A, 0x7FB, 0x5CC, 0x51D, 0x46E, 0x4BF }, { 0x000, 0x0D2, 0x1A4, 0x176, 0x348, 0x39A, 0x2EC, 0x23E, 0x690, 0x642, 0x734, 0x7E6, 0x5D8, 0x50A, 0x47C, 0x4AE }, { 0x000, 0x0D3, 0x1A6, 0x175, 0x34C, 0x39F, 0x2EA, 0x239, 0x698, 0x64B, 0x73E, 0x7ED, 0x5D4, 0x507, 0x472, 0x4A1 }, { 0x000, 0x0D4, 0x1A8, 0x17C, 0x350, 0x384, 0x2F8, 0x22C, 0x6A0, 0x674, 0x708, 0x7DC, 0x5F0, 0x524, 0x458, 0x48C }, { 0x000, 0x0D5, 0x1AA, 0x17F, 0x354, 0x381, 0x2FE, 0x22B, 0x6A8, 0x67D, 0x702, 0x7D7, 0x5FC, 0x529, 0x456, 0x483 }, { 0x000, 0x0D6, 0x1AC, 0x17A, 0x358, 0x38E, 0x2F4, 0x222, 0x6B0, 0x666, 0x71C, 0x7CA, 0x5E8, 0x53E, 0x444, 0x492 }, { 0x000, 0x0D7, 0x1AE, 0x179, 0x35C, 0x38B, 0x2F2, 0x225, 0x6B8, 0x66F, 0x716, 0x7C1, 0x5E4, 0x533, 0x44A, 0x49D }, { 0x000, 0x0D8, 0x1B0, 0x168, 0x360, 0x3B8, 0x2D0, 0x208, 0x6C0, 0x618, 0x770, 0x7A8, 0x5A0, 0x578, 0x410, 0x4C8 }, { 0x000, 0x0D9, 0x1B2, 0x16B, 0x364, 0x3BD, 0x2D6, 0x20F, 0x6C8, 0x611, 0x77A, 0x7A3, 0x5AC, 0x575, 0x41E, 0x4C7 }, { 0x000, 0x0DA, 0x1B4, 0x16E, 0x368, 0x3B2, 0x2DC, 0x206, 0x6D0, 0x60A, 0x764, 0x7BE, 0x5B8, 0x562, 0x40C, 0x4D6 }, { 0x000, 0x0DB, 0x1B6, 0x16D, 0x36C, 0x3B7, 0x2DA, 0x201, 0x6D8, 0x603, 0x76E, 0x7B5, 0x5B4, 0x56F, 0x402, 0x4D9 }, { 0x000, 0x0DC, 0x1B8, 0x164, 0x370, 0x3AC, 0x2C8, 0x214, 0x6E0, 0x63C, 0x758, 0x784, 0x590, 0x54C, 0x428, 0x4F4 }, { 0x000, 0x0DD, 0x1BA, 0x167, 0x374, 0x3A9, 0x2CE, 0x213, 0x6E8, 0x635, 0x752, 0x78F, 0x59C, 0x541, 0x426, 0x4FB }, { 0x000, 0x0DE, 0x1BC, 0x162, 0x378, 0x3A6, 0x2C4, 0x21A, 0x6F0, 0x62E, 0x74C, 0x792, 0x588, 0x556, 0x434, 0x4EA }, { 0x000, 0x0DF, 0x1BE, 0x161, 0x37C, 0x3A3, 0x2C2, 0x21D, 0x6F8, 0x627, 0x746, 0x799, 0x584, 0x55B, 0x43A, 0x4E5 }, { 0x000, 0x0E0, 0x1C0, 0x120, 0x380, 0x360, 0x240, 0x2A0, 0x700, 0x7E0, 0x6C0, 0x620, 0x480, 0x460, 0x540, 0x5A0 }, { 0x000, 0x0E1, 0x1C2, 0x123, 0x384, 0x365, 0x246, 0x2A7, 0x708, 0x7E9, 0x6CA, 0x62B, 0x48C, 0x46D, 0x54E, 0x5AF }, { 0x000, 0x0E2, 0x1C4, 0x126, 0x388, 0x36A, 0x24C, 0x2AE, 0x710, 0x7F2, 0x6D4, 0x636, 0x498, 0x47A, 0x55C, 0x5BE }, { 0x000, 0x0E3, 0x1C6, 0x125, 0x38C, 0x36F, 0x24A, 0x2A9, 0x718, 0x7FB, 0x6DE, 0x63D, 0x494, 0x477, 0x552, 0x5B1 }, { 0x000, 0x0E4, 0x1C8, 0x12C, 0x390, 0x374, 0x258, 0x2BC, 0x720, 0x7C4, 0x6E8, 0x60C, 0x4B0, 0x454, 0x578, 0x59C }, { 0x000, 0x0E5, 0x1CA, 0x12F, 0x394, 0x371, 0x25E, 0x2BB, 0x728, 0x7CD, 0x6E2, 0x607, 0x4BC, 0x459, 0x576, 0x593 }, { 0x000, 0x0E6, 0x1CC, 0x12A, 0x398, 0x37E, 0x254, 0x2B2, 0x730, 0x7D6, 0x6FC, 0x61A, 0x4A8, 0x44E, 0x564, 0x582 }, { 0x000, 0x0E7, 0x1CE, 0x129, 0x39C, 0x37B, 0x252, 0x2B5, 0x738, 0x7DF, 0x6F6, 0x611, 0x4A4, 0x443, 0x56A, 0x58D }, { 0x000, 0x0E8, 0x1D0, 0x138, 0x3A0, 0x348, 0x270, 0x298, 0x740, 0x7A8, 0x690, 0x678, 0x4E0, 0x408, 0x530, 0x5D8 }, { 0x000, 0x0E9, 0x1D2, 0x13B, 0x3A4, 0x34D, 0x276, 0x29F, 0x748, 0x7A1, 0x69A, 0x673, 0x4EC, 0x405, 0x53E, 0x5D7 }, { 0x000, 0x0EA, 0x1D4, 0x13E, 0x3A8, 0x342, 0x27C, 0x296, 0x750, 0x7BA, 0x684, 0x66E, 0x4F8, 0x412, 0x52C, 0x5C6 }, { 0x000, 0x0EB, 0x1D6, 0x13D, 0x3AC, 0x347, 0x27A, 0x291, 0x758, 0x7B3, 0x68E, 0x665, 0x4F4, 0x41F, 0x522, 0x5C9 }, { 0x000, 0x0EC, 0x1D8, 0x134, 0x3B0, 0x35C, 0x268, 0x284, 0x760, 0x78C, 0x6B8, 0x654, 0x4D0, 0x43C, 0x508, 0x5E4 }, { 0x000, 0x0ED, 0x1DA, 0x137, 0x3B4, 0x359, 0x26E, 0x283, 0x768, 0x785, 0x6B2, 0x65F, 0x4DC, 0x431, 0x506, 0x5EB }, { 0x000, 0x0EE, 0x1DC, 0x132, 0x3B8, 0x356, 0x264, 0x28A, 0x770, 0x79E, 0x6AC, 0x642, 0x4C8, 0x426, 0x514, 0x5FA }, { 0x000, 0x0EF, 0x1DE, 0x131, 0x3BC, 0x353, 0x262, 0x28D, 0x778, 0x797, 0x6A6, 0x649, 0x4C4, 0x42B, 0x51A, 0x5F5 }, { 0x000, 0x0F0, 0x1E0, 0x110, 0x3C0, 0x330, 0x220, 0x2D0, 0x780, 0x770, 0x660, 0x690, 0x440, 0x4B0, 0x5A0, 0x550 }, { 0x000, 0x0F1, 0x1E2, 0x113, 0x3C4, 0x335, 0x226, 0x2D7, 0x788, 0x779, 0x66A, 0x69B, 0x44C, 0x4BD, 0x5AE, 0x55F }, { 0x000, 0x0F2, 0x1E4, 0x116, 0x3C8, 0x33A, 0x22C, 0x2DE, 0x790, 0x762, 0x674, 0x686, 0x458, 0x4AA, 0x5BC, 0x54E }, { 0x000, 0x0F3, 0x1E6, 0x115, 0x3CC, 0x33F, 0x22A, 0x2D9, 0x798, 0x76B, 0x67E, 0x68D, 0x454, 0x4A7, 0x5B2, 0x541 }, { 0x000, 0x0F4, 0x1E8, 0x11C, 0x3D0, 0x324, 0x238, 0x2CC, 0x7A0, 0x754, 0x648, 0x6BC, 0x470, 0x484, 0x598, 0x56C }, { 0x000, 0x0F5, 0x1EA, 0x11F, 0x3D4, 0x321, 0x23E, 0x2CB, 0x7A8, 0x75D, 0x642, 0x6B7, 0x47C, 0x489, 0x596, 0x563 }, { 0x000, 0x0F6, 0x1EC, 0x11A, 0x3D8, 0x32E, 0x234, 0x2C2, 0x7B0, 0x746, 0x65C, 0x6AA, 0x468, 0x49E, 0x584, 0x572 }, { 0x000, 0x0F7, 0x1EE, 0x119, 0x3DC, 0x32B, 0x232, 0x2C5, 0x7B8, 0x74F, 0x656, 0x6A1, 0x464, 0x493, 0x58A, 0x57D }, { 0x000, 0x0F8, 0x1F0, 0x108, 0x3E0, 0x318, 0x210, 0x2E8, 0x7C0, 0x738, 0x630, 0x6C8, 0x420, 0x4D8, 0x5D0, 0x528 }, { 0x000, 0x0F9, 0x1F2, 0x10B, 0x3E4, 0x31D, 0x216, 0x2EF, 0x7C8, 0x731, 0x63A, 0x6C3, 0x42C, 0x4D5, 0x5DE, 0x527 }, { 0x000, 0x0FA, 0x1F4, 0x10E, 0x3E8, 0x312, 0x21C, 0x2E6, 0x7D0, 0x72A, 0x624, 0x6DE, 0x438, 0x4C2, 0x5CC, 0x536 }, { 0x000, 0x0FB, 0x1F6, 0x10D, 0x3EC, 0x317, 0x21A, 0x2E1, 0x7D8, 0x723, 0x62E, 0x6D5, 0x434, 0x4CF, 0x5C2, 0x539 }, { 0x000, 0x0FC, 0x1F8, 0x104, 0x3F0, 0x30C, 0x208, 0x2F4, 0x7E0, 0x71C, 0x618, 0x6E4, 0x410, 0x4EC, 0x5E8, 0x514 }, { 0x000, 0x0FD, 0x1FA, 0x107, 0x3F4, 0x309, 0x20E, 0x2F3, 0x7E8, 0x715, 0x612, 0x6EF, 0x41C, 0x4E1, 0x5E6, 0x51B }, { 0x000, 0x0FE, 0x1FC, 0x102, 0x3F8, 0x306, 0x204, 0x2FA, 0x7F0, 0x70E, 0x60C, 0x6F2, 0x408, 0x4F6, 0x5F4, 0x50A }, { 0x000, 0x0FF, 0x1FE, 0x101, 0x3FC, 0x303, 0x202, 0x2FD, 0x7F8, 0x707, 0x606, 0x6F9, 0x404, 0x4FB, 0x5FA, 0x505 } }; // Generated in CLISP: // (dotimes (x 256) // (dotimes (y 16) // (let ((z 0)) // (dotimes (b 4) (when (logbitp b y) (setq z (logxor z (ash x b))))) // (when (zerop (mod y 8)) (format t "~% ")) // (format t " 0x~3,'0X," z)))) #endif // Multiply two GF2-polynomials of degree < 16. #if defined(__sparc__) || defined(__sparc64__) extern "C" uint32 gf2_mul16 (uint16 x, uint16 y); #else uint32 gf2_mul16 (uint16 x, uint16 y) { var uint16 *ptr; // uint16 ptr[0x10]; var uint32 res = 0; // 8 table accesses. ptr = gf2_mul_table[x & 0xFF]; res ^= (uint32)ptr[y & 0xF]; res ^= (uint32)ptr[(y >> 4) & 0xF] << 4; res ^= (uint32)ptr[(y >> 8) & 0xF] << 8; res ^= (uint32)ptr[(y >> 12) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; res ^= (uint32)ptr[y & 0xF] << 8; res ^= (uint32)ptr[(y >> 4) & 0xF] << 12; res ^= (uint32)ptr[(y >> 8) & 0xF] << 16; res ^= (uint32)ptr[(y >> 12) & 0xF] << 20; return res; } #endif // Multiply two GF2-polynomials of degree < 32. // Stores the low part, returns the high part. #if defined(__sparc__) || defined(__sparc64__) extern "C" uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo); #else uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo) { var uint16 *ptr; // uint16 ptr[0x10]; var uint32 hi = 0; var uint32 lo = 0; var uint32 mid = 0; // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0). #if 0 // Standard multiplication, 32 table accesses. ptr = gf2_mul_table[x & 0xFF]; lo ^= (uint32)ptr[y & 0xF]; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4; lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8; lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12; mid ^= (uint32)ptr[(y >> 16) & 0xF]; mid ^= (uint32)ptr[(y >> 20) & 0xF] << 4; mid ^= (uint32)ptr[(y >> 24) & 0xF] << 8; mid ^= (uint32)ptr[(y >> 28) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; lo ^= (uint32)ptr[y & 0xF] << 8; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12; mid ^= (uint32)ptr[(y >> 8) & 0xF]; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 4; mid ^= (uint32)ptr[(y >> 16) & 0xF] << 8; mid ^= (uint32)ptr[(y >> 20) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 24) & 0xF]; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 4; ptr = gf2_mul_table[(x >> 16) & 0xFF]; mid ^= (uint32)ptr[y & 0xF]; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4; mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 16) & 0xF]; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12; ptr = gf2_mul_table[(x >> 24) & 0xFF]; mid ^= (uint32)ptr[y & 0xF] << 8; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 8) & 0xF]; hi ^= (uint32)ptr[(y >> 12) & 0xF] << 4; hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20; #else // Apply Karatsuba: // lo := low16(x)*low16(y) // hi := high16(x)*high16(y) // mid := (high16(x)+low16(x))*(high16(y)+low16(y)) // mid := mid + lo + hi // 24 table accesses. ptr = gf2_mul_table[x & 0xFF]; lo ^= (uint32)ptr[y & 0xF]; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4; lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8; lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; lo ^= (uint32)ptr[y & 0xF] << 8; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12; lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16; lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20; ptr = gf2_mul_table[(x >> 16) & 0xFF]; hi ^= (uint32)ptr[(y >> 16) & 0xF]; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12; ptr = gf2_mul_table[(x >> 24) & 0xFF]; hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20; x ^= x >> 16; y ^= y >> 16; ptr = gf2_mul_table[x & 0xFF]; mid ^= (uint32)ptr[y & 0xF]; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4; mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; mid ^= (uint32)ptr[y & 0xF] << 8; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12; mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20; mid ^= lo; mid ^= hi; #endif *plo = lo ^ (mid << 16); return hi ^ (mid >> 16); } #endif // Multiply two GF2-polynomials of degree < intDsize. // Stores the low part, returns the high part. #if (intDsize==32) #define gf2_mul_uintD gf2_mul32 #endif #if (intDsize==64) inline uint64 gf2_mul32_ (uint32 x, uint32 y) { var uint16 *ptr; // uint16 ptr[0x10]; var uint32 hi = 0; var uint32 lo = 0; var uint32 mid = 0; // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0). // Apply Karatsuba: // lo := low16(x)*low16(y) // hi := high16(x)*high16(y) // mid := (high16(x)+low16(x))*(high16(y)+low16(y)) // mid := mid + lo + hi // 24 table accesses. ptr = gf2_mul_table[x & 0xFF]; lo ^= (uint32)ptr[y & 0xF]; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4; lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8; lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; lo ^= (uint32)ptr[y & 0xF] << 8; lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12; lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16; lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20; ptr = gf2_mul_table[(x >> 16) & 0xFF]; hi ^= (uint32)ptr[(y >> 16) & 0xF]; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12; ptr = gf2_mul_table[(x >> 24) & 0xFF]; hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8; hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12; hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16; hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20; x ^= x >> 16; y ^= y >> 16; ptr = gf2_mul_table[x & 0xFF]; mid ^= (uint32)ptr[y & 0xF]; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4; mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12; ptr = gf2_mul_table[(x >> 8) & 0xFF]; mid ^= (uint32)ptr[y & 0xF] << 8; mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12; mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16; mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20; mid ^= lo; mid ^= hi; return (((uint64)hi << 32) | ((uint64)lo)) ^ ((uint64)mid << 16); } static uintD gf2_mul_uintD (uintD x, uintD y, uintD* plo) { // Apply Karatsuba: // lo := low32(x)*low32(y) // hi := high32(x)*high32(y) // mid := (high32(x)+low32(x))*(high32(y)+low32(y)) // mid := mid + lo + hi // 72 table accesses. var uint64 lo = gf2_mul32_(x,y); var uint64 hi = gf2_mul32_(x>>32,y>>32); var uint64 mid = gf2_mul32_(x^(x>>32),y^(y>>32)); // Result will be (hi << 64) ^ (mid << 32) ^ (lo << 0). *plo = lo ^ (mid << 32); return hi ^ (mid >> 32); } #endif static const _cl_UP gf2_mul (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y) {{ DeclarePoly(cl_GV_MI,x); DeclarePoly(cl_GV_MI,y); var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer; var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer; var uintL xlen = xv->v.length(); var uintL ylen = yv->v.length(); if (xlen == 0) return _cl_UP(UPR, x); if (ylen == 0) return _cl_UP(UPR, y); var cl_heap_modint_ring* R = TheModintRing(UPR->basering()); var uintL len = xlen+ylen-1; var cl_GV_MI result = cl_GV_MI(len,R); var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer; xlen = ceiling(xlen,intDsize); ylen = ceiling(ylen,intDsize); if (xlen < ylen) { var uintL xlen1 = ceiling(len,intDsize)-ylen; // = xlen-{0,1} for (uintL i = 0; i < xlen; i++) { var uintD xw = xv->data[i]; var uintD* rvptr = &rv->data[i]; var uintD carry = 0; for (uintL j = 0; j < ylen; j++) { var uintD rwlo; var uintD rwhi = gf2_mul_uintD(xw,yv->data[j],&rwlo); *rvptr++ ^= carry ^ rwlo; carry = rwhi; } if (i < xlen1) *rvptr ^= carry; } } else { var uintL ylen1 = ceiling(len,intDsize)-xlen; // = ylen-{0,1} for (uintL j = 0; j < ylen; j++) { var uintD yw = yv->data[j]; var uintD* rvptr = &rv->data[j]; var uintD carry = 0; for (uintL i = 0; i < xlen; i++) { var uintD rwlo; var uintD rwhi = gf2_mul_uintD(xv->data[i],yw,&rwlo); *rvptr++ ^= carry ^ rwlo; carry = rwhi; } if (j < ylen1) *rvptr ^= carry; } } return _cl_UP(UPR, result); }} // In characteristic 2, we square a polynomial by doubling the exponents: // (sum(a_i T^i))^2 = sum(a_i^2 T^2i) = sum(a_i T^2i). static uint16 gf2_square_table[0x100] = { 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 }; // Generated in CLISP: // (dotimes (i 256) // (let ((j 0)) // (dotimes (b 8) (when (logbitp b i) (setq j (logior j (ash 1 (+ b b)))))) // (when (zerop (mod i 8)) (format t "~% ")) // (format t " 0x~4,'0X," j))) // Square a GF2-polynomial of degree < intDsize. // Stores the low part, returns the high part. static uintD gf2_square_uintD (uintD x, uintD* lo) { #if (intDsize==32) *lo = ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16) | (uintD)gf2_square_table[x & 0xFF]; x = x>>16; return ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16) | (uintD)gf2_square_table[x & 0xFF]; #endif #if (intDsize==64) *lo = ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48) | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32) | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16) | (uintD)gf2_square_table[x & 0xFF]; x = x>>32; return ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48) | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32) | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16) | (uintD)gf2_square_table[x & 0xFF]; #endif } static const _cl_UP gf2_square (cl_heap_univpoly_ring* UPR, const _cl_UP& x) {{ DeclarePoly(cl_GV_MI,x); var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer; var uintL xlen = xv->v.length(); if (xlen == 0) return _cl_UP(UPR, x); var cl_heap_modint_ring* R = TheModintRing(UPR->basering()); var uintL len = 2*xlen-1; var cl_GV_MI result = cl_GV_MI(len,R); var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer; var uintL count = floor(xlen,intDsize); for (uintL i = 0; i < count; i++) rv->data[2*i+1] = gf2_square_uintD(xv->data[i],&rv->data[2*i]); xlen = xlen%intDsize; if (xlen > 0) { var uintD hiword = xv->data[count]; // xlen bits hiword = gf2_square_uintD(hiword,&rv->data[2*count]); if (xlen > intDsize/2) rv->data[2*count+1] = hiword; } return _cl_UP(UPR, result); }} // Scalar multiplication of GF(2)-polynomials is trivial: 0*y = 0, 1*y = y. static const _cl_UP gf2_scalmul (cl_heap_univpoly_ring* UPR, const cl_ring_element& x, const _cl_UP& y) { if (!(UPR->basering() == x.ring())) cl_abort(); { DeclarePoly(_cl_MI,x); var cl_heap_modint_ring* R = TheModintRing(UPR->basering()); if (R->_zerop(x)) return _cl_UP(UPR, cl_null_GV_I); return y; }} // Evaluation of GF(2)-polynomials is trivial: // At 0, it's the coefficient 0. At 1, it's the sum of all coefficients, // i.e. the parity of the number of nonzero coefficients. static const cl_ring_element gf2_eval (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const cl_ring_element& y) {{ DeclarePoly(cl_GV_MI,x); if (!(UPR->basering() == y.ring())) cl_abort(); { DeclarePoly(_cl_MI,y); var cl_heap_modint_ring* R = TheModintRing(UPR->basering()); var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer; var uintL len = xv->v.length(); if (len==0) return R->zero(); if (R->_zerop(y)) return cl_MI(R, x[0]); else { var uintL count = ceiling(len,intDsize); var uintL bitcount = 0; do { count--; bitcount += logcountD(xv->data[count]); } while (count > 0); return R->canonhom(bitcount%2); } }}} static cl_univpoly_setops gf2_setops = { modint_fprint, gf2_equal }; static cl_univpoly_addops gf2_addops = { modint_zero, modint_zerop, gf2_plus, gf2_minus, gf2_uminus }; static cl_univpoly_mulops gf2_mulops = { modint_one, modint_canonhom, gf2_mul, gf2_square, modint_exptpos }; static cl_univpoly_modulops gf2_modulops = { gf2_scalmul }; static cl_univpoly_polyops gf2_polyops = { modint_degree, modint_ldegree, modint_monomial, modint_coeff, modint_create, modint_set_coeff, modint_finalize, gf2_eval }; class cl_heap_gf2_univpoly_ring : public cl_heap_univpoly_ring { SUBCLASS_cl_heap_univpoly_ring() public: // Constructor. cl_heap_gf2_univpoly_ring (const cl_ring& r) : cl_heap_univpoly_ring (r, &gf2_setops, &gf2_addops, &gf2_mulops, &gf2_modulops, &gf2_polyops) {} }; } // namespace cln