![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gfmul.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [truecrypt] / truecrypt / common|
Return to gfmul.c CVS log | Up to [truecrypt] / truecrypt / common |
1.1 root 1: /*
2: ---------------------------------------------------------------------------
3: Copyright (c) 2003, Dr Brian Gladman, Worcester, UK. All rights reserved.
4:
5: LICENSE TERMS
6:
1.1.1.6 ! root 7: The free distribution and use of this software is allowed (with or without
! 8: changes) provided that:
1.1 root 9:
1.1.1.6 ! root 10: 1. source code distributions include the above copyright notice, this
! 11: list of conditions and the following disclaimer;
1.1 root 12:
1.1.1.6 ! root 13: 2. binary distributions include the above copyright notice, this list
! 14: of conditions and the following disclaimer in their documentation;
! 15:
! 16: 3. the name of the copyright holder is not used to endorse products
! 17: built using this software without specific written permission.
1.1 root 18:
19: DISCLAIMER
20:
21: This software is provided 'as is' with no explicit or implied warranties
22: in respect of its properties, including, but not limited to, correctness
23: and/or fitness for purpose.
24: ---------------------------------------------------------------------------
25: Issue Date: 31/01/2004
26:
27: My thanks to John Viega and David McGrew for their support in developing
28: this code and to David for testing it on a big-endain system.
29: */
30:
31: /*
1.1.1.5 root 32: Portions Copyright (c) 2005 TrueCrypt Foundation
1.1.1.3 root 33:
1.1 root 34: TrueCrypt Foundation made the following changes:
35:
36: - Added multiplication in the finite field GF(2^128) optimized for
37: cases involving a 64-bit operand.
38:
39: - Added multiplication in the finite field GF(2^64).
40:
41: - Added MSB-first mode.
42:
1.1.1.2 root 43: - Added basic test algorithms.
44:
1.1 root 45: - Removed GCM.
46: */
47:
48: #include <memory.h>
1.1.1.5 root 49: #include <stdlib.h>
1.1 root 50: #include "GfMul.h"
51: #include "Tcdefs.h"
1.1.1.3 root 52: #include "Common/Endian.h"
1.1 root 53:
54: /* BUFFER_ALIGN32 or BUFFER_ALIGN64 must be defined at this point to */
55: /* enable faster operation by taking advantage of memory aligned values */
56: /* NOTE: the BUFFER_ALIGN64 option has not been tested extensively */
57:
58: #define BUFFER_ALIGN32
59: #define UNROLL_LOOPS /* define to unroll some loops */
60: #define IN_LINES /* define to use inline functions */
61: /* in place of macros */
62:
63: #define mode(x) GM_##x
64:
65: #if defined(__cplusplus)
66: extern "C"
67: {
68: #endif
69:
70: typedef unsigned __int32 mode(32t);
71: typedef unsigned __int64 mode(64t);
72:
73: #define BRG_LITTLE_ENDIAN 1234 /* byte 0 is least significant (i386) */
74: #define BRG_BIG_ENDIAN 4321 /* byte 0 is most significant (mc68k) */
75:
76: #if BYTE_ORDER == LITTLE_ENDIAN
77: # define PLATFORM_BYTE_ORDER BRG_LITTLE_ENDIAN
78: #endif
79:
80: #if BYTE_ORDER == BIG_ENDIAN
81: # define PLATFORM_BYTE_ORDER BRG_BIG_ENDIAN
82: #endif
83:
84: #ifdef _MSC_VER
85: #pragma intrinsic(memcpy)
86: #define in_line __inline
87: #else
88: #define in_line
89: #endif
90:
91: #if 0 && defined(_MSC_VER)
92: #define rotl32 _lrotl
93: #define rotr32 _lrotr
94: #else
95: #define rotl32(x,n) (((x) << n) | ((x) >> (32 - n)))
96: #define rotr32(x,n) (((x) >> n) | ((x) << (32 - n)))
97: #endif
98:
99: #if !defined(bswap_32)
100: #define bswap_32(x) (rotr32((x), 24) & 0x00ff00ff | rotr32((x), 8) & 0xff00ff00)
101: #endif
102:
103: #if (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
104: #define SWAP_BYTES
105: #else
106: #undef SWAP_BYTES
107: #endif
108:
109: #if defined(SWAP_BYTES)
110:
111: #if defined ( IN_LINES )
112:
113: in_line void bsw_32(void * p, unsigned int n)
114: { unsigned int i = n;
115: while(i--)
116: ((mode(32t)*)p)[i] = bswap_32(((mode(32t)*)p)[i]);
117: }
118:
119: #else
120:
121: #define bsw_32(p,n) \
122: { int _i = (n); while(_i--) ((mode(32t)*)p)[_i] = bswap_32(((mode(32t)*)p)[_i]); }
123:
124: #endif
125:
126: #else
127: #define bsw_32(p,n)
128: #endif
129:
130: /* These values are used to detect long word alignment in order */
131: /* to speed up some GCM buffer operations. This facility may */
132: /* not work on some machines */
133:
134: #define lp08(x) ((unsigned char*)(x))
135: #define lp32(x) ((mode(32t)*)(x))
136: #define lp64(x) ((mode(64t)*)(x))
137:
138: #define A32_MASK 3
139: #define A64_MASK 7
140: #define aligned32(x) (!(((mode(32t))(x)) & A32_MASK))
141: #define aligned64(x) (!(((mode(32t))(x)) & A64_MASK))
142:
143: #if defined( BUFFER_ALIGN32 )
144:
145: #define ADR_MASK A32_MASK
146: #define aligned aligned32
147: #define lp lp32
148: #define lp_inc 4
149:
150: #if defined( IN_LINES )
151:
152: in_line void move_block_aligned( void *p, const void *q)
153: {
154: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1],
155: lp32(p)[2] = lp32(q)[2], lp32(p)[3] = lp32(q)[3];
156: }
157:
158: in_line void move_block_aligned64( void *p, const void *q)
159: {
160: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1];
161: }
162:
163: in_line void xor_block_aligned( void *p, const void *q)
164: {
165: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1],
166: lp32(p)[2] ^= lp32(q)[2], lp32(p)[3] ^= lp32(q)[3];
167: }
168:
169: in_line void xor_block_aligned64( void *p, const void *q)
170: {
171: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1];
172: }
173:
174: #else
175:
176: #define move_block_aligned(p,q) \
177: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1], \
178: lp32(p)[2] = lp32(q)[2], lp32(p)[3] = lp32(q)[3]
179:
180: #define xor_block_aligned(p,q) \
181: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1], \
182: lp32(p)[2] ^= lp32(q)[2], lp32(p)[3] ^= lp32(q)[3]
183:
184: #endif
185:
186: #elif defined( BUFFER_ALIGN64 )
187:
188: #define ADR_MASK A64_MASK
189: #define aligned aligned64
190: #define lp lp64
191: #define lp_inc 8
192:
193: #define move_block_aligned(p,q) \
194: lp64(p)[0] = lp64(q)[0], lp64(p)[1] = lp64(q)[1]
195:
196: #define xor_block_aligned(p,q) \
197: lp64(p)[0] ^= lp64(q)[0], lp64(p)[1] ^= lp64(q)[1]
198:
199: #else
200: #define aligned(x) 0
201: #endif
202:
203: #define move_block(p,q) memcpy((p), (q), BLOCK_LEN)
204:
205: #define xor_block(p,q) \
206: lp08(p)[ 0] ^= lp08(q)[ 0], lp08(p)[ 1] ^= lp08(q)[ 1], \
207: lp08(p)[ 2] ^= lp08(q)[ 2], lp08(p)[ 3] ^= lp08(q)[ 3], \
208: lp08(p)[ 4] ^= lp08(q)[ 4], lp08(p)[ 5] ^= lp08(q)[ 5], \
209: lp08(p)[ 6] ^= lp08(q)[ 6], lp08(p)[ 7] ^= lp08(q)[ 7], \
210: lp08(p)[ 8] ^= lp08(q)[ 8], lp08(p)[ 9] ^= lp08(q)[ 9], \
211: lp08(p)[10] ^= lp08(q)[10], lp08(p)[11] ^= lp08(q)[11], \
212: lp08(p)[12] ^= lp08(q)[12], lp08(p)[13] ^= lp08(q)[13], \
213: lp08(p)[14] ^= lp08(q)[14], lp08(p)[15] ^= lp08(q)[15]
214:
215:
216: #define gf_dat(q) {\
217: q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
218: q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
219: q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
220: q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
221: q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
222: q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
223: q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
224: q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
225: q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
226: q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
227: q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
228: q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
229: q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
230: q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
231: q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
232: q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
233: q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
234: q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
235: q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
236: q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
237: q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
238: q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
239: q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
240: q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
241: q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
242: q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
243: q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
244: q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
245: q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
246: q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
247: q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
248: q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) }
249:
250: /* given the value i in 0..255 as the byte overflow when a a field */
251: /* element in GHASH is multipled by x^8, this function will return */
252: /* the values that are generated in the lo 16-bit word of the field */
253: /* value by applying the modular polynomial. The values lo_byte and */
254: /* hi_byte are returned via the macro xp_fun(lo_byte, hi_byte) so */
255: /* that the values can be assembled into memory as required by a */
256: /* suitable definition of this macro operating on the table above */
257:
258: #define xp(i) xp_fun( \
259: (i & 0x80 ? 0xe1 : 0) ^ (i & 0x40 ? 0x70 : 0) ^ \
260: (i & 0x20 ? 0x38 : 0) ^ (i & 0x10 ? 0x1c : 0) ^ \
261: (i & 0x08 ? 0x0e : 0) ^ (i & 0x04 ? 0x07 : 0) ^ \
262: (i & 0x02 ? 0x03 : 0) ^ (i & 0x01 ? 0x01 : 0), \
263: (i & 0x80 ? 0x00 : 0) ^ (i & 0x40 ? 0x80 : 0) ^ \
264: (i & 0x20 ? 0x40 : 0) ^ (i & 0x10 ? 0x20 : 0) ^ \
265: (i & 0x08 ? 0x10 : 0) ^ (i & 0x04 ? 0x08 : 0) ^ \
266: (i & 0x02 ? 0x84 : 0) ^ (i & 0x01 ? 0xc2 : 0) )
267:
268: #define xp64(i) xp_fun( \
269: (i & 0x80 ? 0xd8 : 0) ^ (i & 0x40 ? 0x6c : 0) ^ \
270: (i & 0x20 ? 0x36 : 0) ^ (i & 0x10 ? 0x1b : 0) ^ \
271: (i & 0x08 ? 0x0d : 0) ^ (i & 0x04 ? 0x06 : 0) ^ \
272: (i & 0x02 ? 0x03 : 0) ^ (i & 0x01 ? 0x01 : 0), \
273: (i & 0x80 ? 0x00 : 0) ^ (i & 0x40 ? 0x00 : 0) ^ \
274: (i & 0x20 ? 0x00 : 0) ^ (i & 0x10 ? 0x00 : 0) ^ \
275: (i & 0x08 ? 0x80 : 0) ^ (i & 0x04 ? 0xc0 : 0) ^ \
276: (i & 0x02 ? 0x60 : 0) ^ (i & 0x01 ? 0xb0 : 0) )
277:
278: static mode(32t) gf_poly[2] = { 0, 0xe1000000 };
279: static mode(32t) gf_poly64[2] = { 0, 0xd8000000 };
280:
281: /* Multiply of a GF128 field element by x. The field element */
282: /* is held in an array of bytes in which field bits 8n..8n + 7 */
283: /* are held in byte[n], with lower indexed bits placed in the */
284: /* more numerically significant bit positions in bytes. */
285:
286: /* This function multiples a field element x, in the polynomial */
287: /* field representation. It uses 32-bit word operations to gain */
288: /* speed but compensates for machine endianess and hence works */
289: /* correctly on both styles of machine */
290:
291: in_line void mul_x(mode(32t) x[4])
292: { mode(32t) t;
293:
294: bsw_32(x, 4);
295:
296: /* at this point the filed element bits 0..127 are set out */
297: /* as follows in 32-bit words (where the most significant */
298: /* (ms) numeric bits are to the left) */
299: /* */
300: /* x[0] x[1] x[2] x[3] */
301: /* ms ls ms ls ms ls ms ls */
302: /* field: 0 ... 31 32 .. 63 64 .. 95 96 .. 127 */
303:
304: t = gf_poly[x[3] & 1]; /* bit 127 of the element */
305: x[3] = (x[3] >> 1) | (x[2] << 31); /* shift bits up by one */
306: x[2] = (x[2] >> 1) | (x[1] << 31); /* position */
307: x[1] = (x[1] >> 1) | (x[0] << 31); /* if bit 7 is 1 xor in */
308: x[0] = (x[0] >> 1) ^ t; /* the field polynomial */
309: bsw_32(x, 4);
310: }
311:
312: in_line void mul_x64(mode(32t) x[2])
313: { mode(32t) t;
314:
315: bsw_32(x, 2);
316:
317: /* at this point the filed element bits 0..127 are set out */
318: /* as follows in 32-bit words (where the most significant */
319: /* (ms) numeric bits are to the left) */
320: /* */
321: /* x[0] x[1] x[2] x[3] */
322: /* ms ls ms ls ms ls ms ls */
323: /* field: 0 ... 31 32 .. 63 64 .. 95 96 .. 127 */
324:
325: t = gf_poly64[x[1] & 1]; /* bit 127 of the element */
326: /* shift bits up by one */
327: /* position */
328: x[1] = (x[1] >> 1) | (x[0] << 31); /* if bit 7 is 1 xor in */
329: x[0] = (x[0] >> 1) ^ t; /* the field polynomial */
330: bsw_32(x, 2);
331: }
332:
333: /* Multiply of a GF128 field element by x^8 using 32-bit words */
334: /* for speed - machine endianess matters here */
335:
336: #if (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
337:
338: #define xp_fun(x,y) ((mode(32t))(x)) | (((mode(32t))(y)) << 8)
339: static const unsigned __int16 gft_le[256] = gf_dat(xp);
340: static const unsigned __int16 gft_le64[256] = gf_dat(xp64);
341:
342: in_line void mul_lex8(mode(32t) x[4]) /* mutiply with long words */
343: { mode(32t) t = (x[3] >> 24); /* in little endian format */
344: x[3] = (x[3] << 8) | (x[2] >> 24);
345: x[2] = (x[2] << 8) | (x[1] >> 24);
346: x[1] = (x[1] << 8) | (x[0] >> 24);
347: x[0] = (x[0] << 8) ^ gft_le[t];
348: }
349:
350: in_line void mul_lex8_64(mode(32t) x[2]) /* mutiply with long words */
351: { mode(32t) t = (x[1] >> 24); /* in little endian format */
352: x[1] = (x[1] << 8) | (x[0] >> 24);
353: x[0] = (x[0] << 8) ^ gft_le64[t];
354: }
355:
356: #endif
357:
358: #if 1 || (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
359:
360: #undef xp_fun
361: #define xp_fun(x,y) ((mode(32t))(y)) | (((mode(32t))(x)) << 8)
362: static const unsigned __int16 gft_be[256] = gf_dat(xp);
363: static const unsigned __int16 gft_be64[256] = gf_dat(xp64);
364:
365: in_line void mul_bex8(mode(32t) x[4]) /* mutiply with long words */
366: { mode(32t) t = (x[3] & 0xff); /* in big endian format */
367: x[3] = (x[3] >> 8) | (x[2] << 24);
368: x[2] = (x[2] >> 8) | (x[1] << 24);
369: x[1] = (x[1] >> 8) | (x[0] << 24);
370: x[0] = (x[0] >> 8) ^ (((mode(32t))gft_be[t]) << 16);
371: }
372:
373: in_line void mul_bex8_64(mode(32t) x[2]) /* mutiply with long words */
374: { mode(32t) t = (x[1] & 0xff); /* in big endian format */
375: x[1] = (x[1] >> 8) | (x[0] << 24);
376: x[0] = (x[0] >> 8) ^ (((mode(32t))gft_be64[t]) << 16);
377: }
378:
379: #endif
380:
381: /* hence choose the correct version for the machine endianess */
382:
383: #if PLATFORM_BYTE_ORDER == BRG_BIG_ENDIAN
384: #define mul_x8 mul_bex8
385: #define mul_x8_64 mul_bex8_64
386: #else
387: #define mul_x8 mul_lex8
388: #define mul_x8_64 mul_lex8_64
389: #endif
390:
391: /* different versions of the general gf_mul function are provided */
392: /* here. Sadly none are very fast :-( */
393:
394: void GfMul128 (void *a, const void* b)
395: { mode(32t) r[CBLK_LEN >> 2], p[8][CBLK_LEN >> 2];
396: int i;
397:
398: move_block_aligned(p[0], b);
399: bsw_32(p[0], 4);
400: for(i = 0; i < 7; ++i)
401: {
402: p[i + 1][3] = (p[i][3] >> 1) | (p[i][2] << 31);
403: p[i + 1][2] = (p[i][2] >> 1) | (p[i][1] << 31);
404: p[i + 1][1] = (p[i][1] >> 1) | (p[i][0] << 31);
405: p[i + 1][0] = (p[i][0] >> 1) ^ gf_poly[p[i][3] & 1];
406: }
407:
408: memset(r, 0, CBLK_LEN);
409: for(i = 0; i < 16; ++i)
410: {
411: if(i) mul_bex8(r); /* order is always big endian here */
412:
413: if(((unsigned char*)a)[15 - i] & 0x80)
414: xor_block_aligned(r, p[0]);
415: if(((unsigned char*)a)[15 - i] & 0x40)
416: xor_block_aligned(r, p[1]);
417: if(((unsigned char*)a)[15 - i] & 0x20)
418: xor_block_aligned(r, p[2]);
419: if(((unsigned char*)a)[15 - i] & 0x10)
420: xor_block_aligned(r, p[3]);
421: if(((unsigned char*)a)[15 - i] & 0x08)
422: xor_block_aligned(r, p[4]);
423: if(((unsigned char*)a)[15 - i] & 0x04)
424: xor_block_aligned(r, p[5]);
425: if(((unsigned char*)a)[15 - i] & 0x02)
426: xor_block_aligned(r, p[6]);
427: if(((unsigned char*)a)[15 - i] & 0x01)
428: xor_block_aligned(r, p[7]);
429: }
430: bsw_32(r, 4);
431: move_block_aligned(a, r);
432: }
433:
434: #if defined( UNROLL_LOOPS )
435:
436: #define xor_8k(i) \
437: xor_block_aligned(r, ctx->gf_t8k[i + i][a[i] & 15]); \
438: xor_block_aligned(r, ctx->gf_t8k[i + i + 1][a[i] >> 4])
439:
440:
441: void GfMul128Tab (unsigned char a[CBLK_LEN], GfCtx8k *ctx)
442: { unsigned __int32 r[CBLK_LEN >> 2];
443:
444: move_block_aligned(r, ctx->gf_t8k[0][a[0] & 15]);
445: xor_block_aligned(r, ctx->gf_t8k[1][a[0] >> 4]);
446: xor_8k( 1); xor_8k( 2); xor_8k( 3);
447: xor_8k( 4); xor_8k( 5); xor_8k( 6); xor_8k( 7);
448: xor_8k( 8); xor_8k( 9); xor_8k(10); xor_8k(11);
449: xor_8k(12); xor_8k(13); xor_8k(14); xor_8k(15);
450: move_block_aligned(a, r);
451: }
452:
453: #else
454:
455: void GfMul128Tab (unsigned char a[CBLK_LEN], GfCtx8k *ctx)
456: { unsigned __int32 r[CBLK_LEN >> 2], *p;
457: int i;
458:
459: p = ctx->gf_t8k[0][a[0] & 15];
460: memcpy(r, p, CBLK_LEN);
461: p = ctx->gf_t8k[1][a[0] >> 4];
462: xor_block_aligned(r, p);
463: for(i = 1; i < CBLK_LEN; ++i)
464: {
465: xor_block_aligned(r, ctx->gf_t8k[i + i][a[i] & 15]);
466: xor_block_aligned(r, ctx->gf_t8k[i + i + 1][a[i] >> 4]);
467: }
468: memcpy(a, r, CBLK_LEN);
469: }
470:
471: #endif
472:
473: void compile_8k_table(unsigned __int8 *a, GfCtx8k *ctx)
474: { int i, j, k;
475:
476: memset(ctx->gf_t8k, 0, 32 * 16 * 16);
477: for(i = 0; i < 2 * CBLK_LEN; ++i)
478: {
479: if(i == 0)
480: {
481: memcpy(ctx->gf_t8k[1][8], a, CBLK_LEN);
482: for(j = 4; j > 0; j >>= 1)
483: {
484: memcpy(ctx->gf_t8k[1][j], ctx->gf_t8k[1][j + j], CBLK_LEN);
485: mul_x(ctx->gf_t8k[1][j]);
486: }
487: memcpy(ctx->gf_t8k[0][8], ctx->gf_t8k[1][1], CBLK_LEN);
488: mul_x(ctx->gf_t8k[0][8]);
489: for(j = 4; j > 0; j >>= 1)
490: {
491: memcpy(ctx->gf_t8k[0][j], ctx->gf_t8k[0][j + j], CBLK_LEN);
492: mul_x(ctx->gf_t8k[0][j]);
493: }
494: }
495: else if(i > 1)
496: for(j = 8; j > 0; j >>= 1)
497: {
498: memcpy(ctx->gf_t8k[i][j], ctx->gf_t8k[i - 2][j], CBLK_LEN);
499: mul_x8(ctx->gf_t8k[i][j]);
500: }
501:
502: for(j = 2; j < 16; j += j)
503: {
504: mode(32t) *pj = ctx->gf_t8k[i][j];
505: mode(32t) *pk = ctx->gf_t8k[i][1];
506: mode(32t) *pl = ctx->gf_t8k[i][j + 1];
507:
508: for(k = 1; k < j; ++k)
509: {
510: *pl++ = pj[0] ^ *pk++;
511: *pl++ = pj[1] ^ *pk++;
512: *pl++ = pj[2] ^ *pk++;
513: *pl++ = pj[3] ^ *pk++;
514: }
515: }
516: }
517: }
518:
519:
520: void compile_4k_table64(unsigned __int8 *a, GfCtx4k64 *ctx)
521: { int i, j, k;
522:
523: memset(ctx->gf_t4k, 0, sizeof(ctx->gf_t4k));
524: for(i = 0; i < 2 * CBLK_LEN8; ++i)
525: {
526: if(i == 0)
527: {
528: memcpy(ctx->gf_t4k[1][8], a, CBLK_LEN8);
529: for(j = 4; j > 0; j >>= 1)
530: {
531: memcpy(ctx->gf_t4k[1][j], ctx->gf_t4k[1][j + j], CBLK_LEN8);
532: mul_x64(ctx->gf_t4k[1][j]);
533: }
534: memcpy(ctx->gf_t4k[0][8], ctx->gf_t4k[1][1], CBLK_LEN8);
535: mul_x64(ctx->gf_t4k[0][8]);
536: for(j = 4; j > 0; j >>= 1)
537: {
538: memcpy(ctx->gf_t4k[0][j], ctx->gf_t4k[0][j + j], CBLK_LEN8);
539: mul_x64(ctx->gf_t4k[0][j]);
540: }
541: }
542: else if(i > 1)
543: for(j = 8; j > 0; j >>= 1)
544: {
545: memcpy(ctx->gf_t4k[i][j], ctx->gf_t4k[i - 2][j], CBLK_LEN8);
546: mul_x8_64(ctx->gf_t4k[i][j]);
547: }
548:
549: for(j = 2; j < 16; j += j)
550: {
551: mode(32t) *pj = ctx->gf_t4k[i][j];
552: mode(32t) *pk = ctx->gf_t4k[i][1];
553: mode(32t) *pl = ctx->gf_t4k[i][j + 1];
554:
555: for(k = 1; k < j; ++k)
556: {
557: *pl++ = pj[0] ^ *pk++;
558: *pl++ = pj[1] ^ *pk++;
559: *pl++ = pj[2] ^ *pk++;
560: *pl++ = pj[3] ^ *pk++;
561: }
562: }
563: }
564: }
565:
566: static int IsBitSet128 (unsigned int bit, unsigned __int8 *a)
567: {
568: return a[(127 - bit) / 8] & (0x80 >> ((127 - bit) % 8));
569: }
570:
571: static int IsBitSet64 (unsigned int bit, unsigned __int8 *a)
572: {
573: return a[(63 - bit) / 8] & (0x80 >> ((63 - bit) % 8));
574: }
575:
576: static void SetBit128 (unsigned int bit, unsigned __int8 *a)
577: {
578: a[(127 - bit) / 8] |= 0x80 >> ((127 - bit) % 8);
579: }
580:
581: static void SetBit64 (unsigned int bit, unsigned __int8 *a)
582: {
583: a[(63 - bit) / 8] |= 0x80 >> ((63 - bit) % 8);
584: }
585:
1.1.1.2 root 586: void MirrorBits128 (unsigned __int8 *a)
1.1 root 587: {
588: unsigned __int8 t[128 / 8];
589: int i;
590: memset (t,0,16);
591: for (i = 0; i < 128; i++)
592: {
593: if (IsBitSet128(i, a))
594: SetBit128 (127 - i, t);
595: }
596: memcpy (a, t, sizeof (t));
597: burn (t,sizeof (t));
598: }
599:
600: void MirrorBits64 (unsigned __int8 *a)
601: {
602: unsigned __int8 t[64 / 8];
603: int i;
604: memset (t,0,8);
605: for (i = 0; i < 64; i++)
606: {
607: if (IsBitSet64(i, a))
608: SetBit64 (63 - i, t);
609: }
610: memcpy (a, t, sizeof (t));
611: burn (t,sizeof (t));
612: }
613:
614: /* Allocate and initialize speed optimization table
615: for multiplication by 64-bit operand in MSB-first mode */
616: int Gf128Tab64Init (unsigned __int8 *a, GfCtx *ctx)
617: {
618: GfCtx8k *ctx8k;
619: unsigned __int8 am[16];
620: int i, j;
621:
622: ctx8k = (GfCtx8k *) TCalloc (sizeof (GfCtx8k));
623: if (!ctx8k)
624: return FALSE;
625:
626: memcpy (am, a, 16);
627: MirrorBits128 (am);
628: compile_8k_table (am, ctx8k);
629:
630: /* Convert 8k LSB-first table to 4k MSB-first */
631: for (i = 16; i < 32; i++)
632: {
633: for (j = 0; j < 16; j++)
634: {
635: int jm = 0;
636: jm |= (j & 0x1) << 3;
637: jm |= (j & 0x2) << 1;
638: jm |= (j & 0x4) >> 1;
639: jm |= (j & 0x8) >> 3;
640:
641: memcpy (&ctx->gf_t128[i-16][jm], (unsigned char *)&ctx8k->gf_t8k[31-i][j], 16);
642: MirrorBits128 ((unsigned char *)&ctx->gf_t128[i-16][jm]);
643: }
644: }
645:
646: burn (ctx8k ,sizeof (*ctx8k));
647: burn (am, sizeof (am));
648: TCfree (ctx8k);
649: return TRUE;
650: }
651:
652: int Gf64TabInit (unsigned __int8 *a, GfCtx *ctx)
653: {
1.1.1.4 root 654: /* Deprecated/legacy */
655:
1.1 root 656: GfCtx4k64 *ctx4k;
657: unsigned __int8 am[8];
658: int i, j;
659:
660: ctx4k = (GfCtx4k64 *) TCalloc (sizeof (GfCtx4k64));
661: if (!ctx4k)
662: return FALSE;
663:
664: memcpy (am, a, 8);
665: MirrorBits64 (am);
666: compile_4k_table64 (am, ctx4k);
667:
668: /* Convert LSB-first table to MSB-first */
669: for (i = 0; i < 16; i++)
670: {
671: for (j = 0; j < 16; j++)
672: {
673: int jm = 0;
674: jm |= (j & 0x1) << 3;
675: jm |= (j & 0x2) << 1;
676: jm |= (j & 0x4) >> 1;
677: jm |= (j & 0x8) >> 3;
678:
679: memcpy (&ctx->gf_t64[i][jm], (unsigned char *)&ctx4k->gf_t4k[15-i][j], 8);
680: MirrorBits64 ((unsigned char *)&ctx->gf_t64[i][jm]);
681: }
682: }
683:
684: burn (ctx4k,sizeof (*ctx4k));
685: burn (am, sizeof (am));
686: TCfree (ctx4k);
687: return TRUE;
688: }
689:
690: #define xor_8kt64(i) \
691: xor_block_aligned(r, ctx->gf_t128[i + i][a[i] & 15]); \
692: xor_block_aligned(r, ctx->gf_t128[i + i + 1][a[i] >> 4])
693:
694: /* Multiply a 128-bit number by a 64-bit number in the finite field GF(2^128) */
695: void Gf128MulBy64Tab (unsigned __int8 a[8], unsigned __int8 p[16], GfCtx *ctx)
696: {
697: unsigned __int32 r[CBLK_LEN >> 2];
698:
699: move_block_aligned(r, ctx->gf_t128[7*2][a[7] & 15]);
700: xor_block_aligned(r, ctx->gf_t128[7*2+1][a[7] >> 4]);
701:
702: if (*(unsigned __int16 *)a)
703: {
704: xor_8kt64(0);
705: xor_8kt64(1);
706: }
707: if (a[2])
708: {
709: xor_8kt64(2);
710: }
711: xor_8kt64(3);
712: xor_8kt64(4);
713: xor_8kt64(5);
714: xor_8kt64(6);
715:
716: move_block_aligned(p, r);
717: }
718:
719: #define xor_8k64(i) \
720: xor_block_aligned64(r, ctx->gf_t64[i + i][a[i] & 15]); \
721: xor_block_aligned64(r, ctx->gf_t64[i + i + 1][a[i] >> 4])
722:
723: /* Multiply two 64-bit numbers in the finite field GF(2^64) */
724: void Gf64MulTab (unsigned char a[8], unsigned char p[8], GfCtx *ctx)
725: {
1.1.1.4 root 726: /* Deprecated/legacy */
727:
1.1 root 728: unsigned __int32 r[CBLK_LEN8 >> 2];
729:
730: move_block_aligned64(r, ctx->gf_t64[7*2][a[7] & 15]);
731: xor_block_aligned64(r, ctx->gf_t64[7*2+1][a[7] >> 4]);
732:
733: if (*(unsigned __int16 *)a)
734: {
735: xor_8k64(0);
736: xor_8k64(1);
737: }
738: if (a[2])
739: {
740: xor_8k64(2);
741: }
742: xor_8k64(3);
743: xor_8k64(4);
744: xor_8k64(5);
745: xor_8k64(6);
746:
747: move_block_aligned64(p, r);
748: }
749:
750:
751: /* Basic algorithms for testing of optimized algorithms */
752:
753: static void xor128 (unsigned __int64 *a, unsigned __int64 *b)
754: {
755: *a++ ^= *b++;
756: *a ^= *b;
757: }
758:
759: static void shl128 (unsigned __int8 *a)
760: {
761: int i, x = 0, xx;
762: for (i = 15; i >= 0; i--)
763: {
764: xx = (a[i] & 0x80) >> 7;
765: a[i] = (a[i] << 1) | x;
766: x = xx;
767: }
768: }
769:
770: static void GfMul128Basic (unsigned __int8 *a, unsigned __int8 *b, unsigned __int8 *p)
771: {
772: int i;
773: unsigned __int8 la[16];
774: memcpy (la, a, 16);
775: memset (p, 0, 16);
776:
777: for (i = 0; i < 128; i++)
778: {
779: if (IsBitSet128 (i, b))
780: xor128 ((unsigned __int64 *)p, (unsigned __int64 *)la);
781:
782: if (la[0] & 0x80)
783: {
784: shl128 (la);
785: la[15] ^= 0x87;
786: }
787: else
788: {
789: shl128 (la);
790: }
791: }
792: }
793:
794: static void xor64 (unsigned __int64 *a, unsigned __int64 *b)
795: {
796: *a ^= *b;
797: }
798:
799: static void shl64 (unsigned __int8 *a)
800: {
801: int i, x = 0, xx;
802: for (i = 7; i >= 0; i--)
803: {
804: xx = (a[i] & 0x80) >> 7;
805: a[i] = (a[i] << 1) | x;
806: x = xx;
807: }
808: }
809:
810: static void GfMul64Basic (unsigned __int8 *a, unsigned __int8 *b, unsigned __int8* p)
811: {
1.1.1.4 root 812: /* Deprecated/legacy */
813:
1.1 root 814: int i;
815: unsigned __int8 la[8];
816: memcpy (la, a, 8);
817: memset (p, 0, 8);
818:
819: for (i = 0; i < 64; i++)
820: {
821: if (IsBitSet64 (i, b))
822: xor64 ((unsigned __int64 *)p, (unsigned __int64 *)la);
823:
824: if (la[0] & 0x80)
825: {
826: shl64 (la);
827: la[7] ^= 0x1b;
828: }
829: else
830: {
831: shl64 (la);
832: }
833: }
834: }
835:
836:
837: BOOL GfMulSelfTest ()
838: {
839: BOOL result = TRUE;
840: unsigned __int8 a[16];
841: unsigned __int8 b[16];
842: unsigned __int8 p1[16];
843: unsigned __int8 p2[16];
844: GfCtx *gfCtx = (GfCtx *) TCalloc (sizeof (GfCtx));
845: int i, j;
846:
847: if (!gfCtx)
848: return FALSE;
849:
1.1.1.4 root 850: /* GF(2^64) - deprecated/legacy */
1.1 root 851: for (i = 0; i < 0x100; i++)
852: {
853: for (j = 0; j < 8; j++)
854: {
855: a[j] = (unsigned __int8) i;
856: b[j] = a[j] ^ 0xff;
857: }
858:
859: GfMul64Basic (a, b, p1);
860:
861: Gf64TabInit (a, gfCtx);
862: Gf64MulTab (b, p2, gfCtx);
863:
864: if (memcmp (p1, p2, 8) != 0)
865: result = FALSE;
866: }
867:
868: /* GF(2^128) */
869: for (i = 0; i < 0x100; i++)
870: {
871: for (j = 0; j < 16; j++)
872: {
873: a[j] = (unsigned __int8) i;
874: b[j] = j < 8 ? 0 : a[j] ^ 0xff;
875: }
876:
877: GfMul128Basic (a, b, p1);
878:
879: Gf128Tab64Init (a, gfCtx);
880: Gf128MulBy64Tab (b + 8, p2, gfCtx);
881:
882: if (memcmp (p1, p2, 16) != 0)
883: result = FALSE;
884: }
885:
886: TCfree (gfCtx);
887: return result;
888: }
889:
890: #if defined(__cplusplus)
891: }
892: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.