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