+/*
+ * Precomputed window: k*G points, where G is the curve generator, and k
+ * is an integer from 1 to 15 (inclusive). The X and Y coordinates of
+ * the point are encoded as 20 words of 13 bits each (little-endian
+ * order); 13-bit words are then grouped 2-by-2 into 32-bit words
+ * (little-endian order within each word).
+ */
+static const uint32_t Gwin[15][20] = {
+
+ { 0x04C60296, 0x02721176, 0x19D00F4A, 0x102517AC,
+ 0x13B8037D, 0x0748103C, 0x1E730E56, 0x08481FE2,
+ 0x0F97012C, 0x00D605F4, 0x1DFA11F5, 0x0C801A0D,
+ 0x0F670CBB, 0x0AED0CC5, 0x115E0E33, 0x181F0785,
+ 0x13F514A7, 0x0FF30E3B, 0x17171E1A, 0x009F18D0 },
+
+ { 0x1B341978, 0x16911F11, 0x0D9A1A60, 0x1C4E1FC8,
+ 0x1E040969, 0x096A06B0, 0x091C0030, 0x09EF1A29,
+ 0x18C40D03, 0x00F91C9E, 0x13C313D1, 0x096F0748,
+ 0x011419E0, 0x1CC713A6, 0x1DD31DAD, 0x1EE80C36,
+ 0x1ECD0C69, 0x1A0800A4, 0x08861B8E, 0x000E1DD5 },
+
+ { 0x173F1D6C, 0x02CC06F1, 0x14C21FB4, 0x043D1EB6,
+ 0x0F3606B7, 0x1A971C59, 0x1BF71951, 0x01481323,
+ 0x068D0633, 0x00BD12F9, 0x13EA1032, 0x136209E8,
+ 0x1C1E19A7, 0x06C7013E, 0x06C10AB0, 0x14C908BB,
+ 0x05830CE1, 0x1FEF18DD, 0x00620998, 0x010E0D19 },
+
+ { 0x18180852, 0x0604111A, 0x0B771509, 0x1B6F0156,
+ 0x00181FE2, 0x1DCC0AF4, 0x16EF0659, 0x11F70E80,
+ 0x11A912D0, 0x01C414D2, 0x027618C6, 0x05840FC6,
+ 0x100215C4, 0x187E0C3B, 0x12771C96, 0x150C0B5D,
+ 0x0FF705FD, 0x07981C67, 0x1AD20C63, 0x01C11C55 },
+
+ { 0x1E8113ED, 0x0A940370, 0x12920215, 0x1FA31D6F,
+ 0x1F7C0C82, 0x10CD03F7, 0x02640560, 0x081A0B5E,
+ 0x1BD21151, 0x00A21642, 0x0D0B0DA4, 0x0176113F,
+ 0x04440D1D, 0x001A1360, 0x1068012F, 0x1F141E49,
+ 0x10DF136B, 0x0E4F162B, 0x0D44104A, 0x01C1105F },
+
+ { 0x011411A9, 0x01551A4F, 0x0ADA0C6B, 0x01BD0EC8,
+ 0x18120C74, 0x112F1778, 0x099202CB, 0x0C05124B,
+ 0x195316A4, 0x01600685, 0x1E3B1FE2, 0x189014E3,
+ 0x0B5E1FD7, 0x0E0311F8, 0x08E000F7, 0x174E00DE,
+ 0x160702DF, 0x1B5A15BF, 0x03A11237, 0x01D01704 },
+
+ { 0x0C3D12A3, 0x0C501C0C, 0x17AD1300, 0x1715003F,
+ 0x03F719F8, 0x18031ED8, 0x1D980667, 0x0F681896,
+ 0x1B7D00BF, 0x011C14CE, 0x0FA000B4, 0x1C3501B0,
+ 0x0D901C55, 0x06790C10, 0x029E0736, 0x0DEB0400,
+ 0x034F183A, 0x030619B4, 0x0DEF0033, 0x00E71AC7 },
+
+ { 0x1B7D1393, 0x1B3B1076, 0x0BED1B4D, 0x13011F3A,
+ 0x0E0E1238, 0x156A132B, 0x013A02D3, 0x160A0D01,
+ 0x1CED1EE9, 0x00C5165D, 0x184C157E, 0x08141A83,
+ 0x153C0DA5, 0x1ED70F9D, 0x05170D51, 0x02CF13B8,
+ 0x18AE1771, 0x1B04113F, 0x05EC11E9, 0x015A16B3 },
+
+ { 0x04A41EE0, 0x1D1412E4, 0x1C591D79, 0x118511B7,
+ 0x14F00ACB, 0x1AE31E1C, 0x049C0D51, 0x016E061E,
+ 0x1DB71EDF, 0x01D41A35, 0x0E8208FA, 0x14441293,
+ 0x011F1E85, 0x1D54137A, 0x026B114F, 0x151D0832,
+ 0x00A50964, 0x1F9C1E1C, 0x064B12C9, 0x005409D1 },
+
+ { 0x062B123F, 0x0C0D0501, 0x183704C3, 0x08E31120,
+ 0x0A2E0A6C, 0x14440FED, 0x090A0D1E, 0x13271964,
+ 0x0B590A3A, 0x019D1D9B, 0x05780773, 0x09770A91,
+ 0x0F770CA3, 0x053F19D4, 0x02C80DED, 0x1A761304,
+ 0x091E0DD9, 0x15D201B8, 0x151109AA, 0x010F0198 },
+
+ { 0x05E101D1, 0x072314DD, 0x045F1433, 0x1A041541,
+ 0x10B3142E, 0x01840736, 0x1C1B19DB, 0x098B0418,
+ 0x1DBC083B, 0x007D1444, 0x01511740, 0x11DD1F3A,
+ 0x04ED0E2F, 0x1B4B1A62, 0x10480D04, 0x09E911A2,
+ 0x04211AFA, 0x19140893, 0x04D60CC4, 0x01210648 },
+
+ { 0x112703C4, 0x018B1BA1, 0x164C1D50, 0x05160BE0,
+ 0x0BCC1830, 0x01CB1554, 0x13291732, 0x1B2B1918,
+ 0x0DED0817, 0x00E80775, 0x0A2401D3, 0x0BFE08B3,
+ 0x0E531199, 0x058616E9, 0x04770B91, 0x110F0C55,
+ 0x19C11554, 0x0BFB1159, 0x03541C38, 0x000E1C2D },
+
+ { 0x10390C01, 0x02BB0751, 0x0AC5098E, 0x096C17AB,
+ 0x03C90E28, 0x10BD18BF, 0x002E1F2D, 0x092B0986,
+ 0x1BD700AC, 0x002E1F20, 0x1E3D1FD8, 0x077718BB,
+ 0x06F919C4, 0x187407ED, 0x11370E14, 0x081E139C,
+ 0x00481ADB, 0x14AB0289, 0x066A0EBE, 0x00C70ED6 },
+
+ { 0x0694120B, 0x124E1CC9, 0x0E2F0570, 0x17CF081A,
+ 0x078906AC, 0x066D17CF, 0x1B3207F4, 0x0C5705E9,
+ 0x10001C38, 0x00A919DE, 0x06851375, 0x0F900BD8,
+ 0x080401BA, 0x0EEE0D42, 0x1B8B11EA, 0x0B4519F0,
+ 0x090F18C0, 0x062E1508, 0x0DD909F4, 0x01EB067C },
+
+ { 0x0CDC1D5F, 0x0D1818F9, 0x07781636, 0x125B18E8,
+ 0x0D7003AF, 0x13110099, 0x1D9B1899, 0x175C1EB7,
+ 0x0E34171A, 0x01E01153, 0x081A0F36, 0x0B391783,
+ 0x1D1F147E, 0x19CE16D7, 0x11511B21, 0x1F2C10F9,
+ 0x12CA0E51, 0x05A31D39, 0x171A192E, 0x016B0E4F }
+};
+
+/*
+ * Lookup one of the Gwin[] values, by index. This is constant-time.
+ */
+static void
+lookup_Gwin(p256_jacobian *T, uint32_t idx)
+{
+ uint32_t xy[20];
+ uint32_t k;
+ size_t u;
+
+ memset(xy, 0, sizeof xy);
+ for (k = 0; k < 15; k ++) {
+ uint32_t m;
+
+ m = -EQ(idx, k + 1);
+ for (u = 0; u < 20; u ++) {
+ xy[u] |= m & Gwin[k][u];
+ }
+ }
+ for (u = 0; u < 10; u ++) {
+ T->x[(u << 1) + 0] = xy[u] & 0xFFFF;
+ T->x[(u << 1) + 1] = xy[u] >> 16;
+ T->y[(u << 1) + 0] = xy[u + 10] & 0xFFFF;
+ T->y[(u << 1) + 1] = xy[u + 10] >> 16;
+ }
+ memset(T->z, 0, sizeof T->z);
+ T->z[0] = 1;
+}
+
+/*
+ * Multiply the generator by an integer. The integer is assumed non-zero
+ * and lower than the curve order.
+ */
+static void
+p256_mulgen(p256_jacobian *P, const unsigned char *x, size_t xlen)
+{
+ /*
+ * qz is a flag that is initially 1, and remains equal to 1
+ * as long as the point is the point at infinity.
+ *
+ * We use a 4-bit window to handle multiplier bits by groups
+ * of 4. The precomputed window is constant static data, with
+ * points in affine coordinates; we use a constant-time lookup.
+ */
+ p256_jacobian Q;
+ uint32_t qz;
+
+ memset(&Q, 0, sizeof Q);
+ qz = 1;
+ while (xlen -- > 0) {
+ int k;
+ unsigned bx;
+
+ bx = *x ++;
+ for (k = 0; k < 2; k ++) {
+ uint32_t bits;
+ uint32_t bnz;
+ p256_jacobian T, U;
+
+ p256_double(&Q);
+ p256_double(&Q);
+ p256_double(&Q);
+ p256_double(&Q);
+ bits = (bx >> 4) & 0x0F;
+ bnz = NEQ(bits, 0);
+ lookup_Gwin(&T, bits);
+ U = Q;
+ p256_add_mixed(&U, &T);
+ CCOPY(bnz & qz, &Q, &T, sizeof Q);
+ CCOPY(bnz & ~qz, &Q, &U, sizeof Q);
+ qz &= ~bnz;
+ bx <<= 4;
+ }
+ }
+ *P = Q;
+}
+