// 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);
// Destructor.
~cl_heap_gf2_univpoly_ring () {}
};
static void cl_heap_gf2_univpoly_ring_destructor (cl_heap* pointer)
{
(*(cl_heap_gf2_univpoly_ring*)pointer).~cl_heap_gf2_univpoly_ring();
}
cl_class cl_class_gf2_univpoly_ring = {
cl_heap_gf2_univpoly_ring_destructor,
cl_class_flags_univpoly_ring
};
// Constructor.
inline cl_heap_gf2_univpoly_ring::cl_heap_gf2_univpoly_ring (const cl_ring& r)
: cl_heap_univpoly_ring (r, &gf2_setops, &gf2_addops, &gf2_mulops, &gf2_modulops, &gf2_polyops)
{
type = &cl_class_gf2_univpoly_ring;
}
} // namespace cln
syntax highlighted by Code2HTML, v. 0.9.1