nfold.c revision 7934:6aeeafc994de 
1/*
2 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
3 * Use is subject to license terms.
4 */
5
6
7/*
8 * Copyright (C) 1998 by the FundsXpress, INC.
9 *
10 * All rights reserved.
11 *
12 * Export of this software from the United States of America may require
13 * a specific license from the United States Government.  It is the
14 * responsibility of any person or organization contemplating export to
15 * obtain such a license before exporting.
16 *
17 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
18 * distribute this software and its documentation for any purpose and
19 * without fee is hereby granted, provided that the above copyright
20 * notice appear in all copies and that both that copyright notice and
21 * this permission notice appear in supporting documentation, and that
22 * the name of FundsXpress. not be used in advertising or publicity pertaining
23 * to distribution of the software without specific, written prior
24 * permission.  FundsXpress makes no representations about the suitability of
25 * this software for any purpose.  It is provided "as is" without express
26 * or implied warranty.
27 *
28 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
29 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
30 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
31 */
32
33#include "k5-int.h"
34
35/*
36 * Solaris Kerberos defines memory management macros in <krb5.h>,
37 * which is included by <k5-int.h>, so we need not include <memory.h>
38 */
39/* #include <memory.h> */
40
41/*
42n-fold(k-bits):
43  l = lcm(n,k)
44  r = l/k
45  s = k-bits | k-bits rot 13 | k-bits rot 13*2 | ... | k-bits rot 13*(r-1)
46  compute the 1's complement sum:
47	n-fold = s[0..n-1]+s[n..2n-1]+s[2n..3n-1]+..+s[(k-1)*n..k*n-1]
48*/
49
50/* representation: msb first, assume n and k are multiples of 8, and
51   that k>=16.  this is the case of all the cryptosystems which are
52   likely to be used.  this function can be replaced if that
53   assumption ever fails.  */
54
55/* input length is in bits */
56
57void
58krb5_nfold(unsigned int inbits, const unsigned char *in, unsigned int outbits,
59	   unsigned char *out)
60{
61    int a,b,c,lcm;
62    int byte, i, msbit;
63
64    /* the code below is more readable if I make these bytes
65       instead of bits */
66
67    inbits >>= 3;
68    outbits >>= 3;
69
70    /* first compute lcm(n,k) */
71
72    a = outbits;
73    b = inbits;
74
75    while(b != 0) {
76	c = b;
77	b = a%b;
78	a = c;
79    }
80
81    lcm = outbits*inbits/a;
82
83    /* now do the real work */
84
85    (void) memset(out, 0, outbits);
86    byte = 0;
87
88    /* this will end up cycling through k lcm(k,n)/k times, which
89       is correct */
90    for (i=lcm-1; i>=0; i--) {
91	/* compute the msbit in k which gets added into this byte */
92	msbit = (/* first, start with the msbit in the first, unrotated
93		    byte */
94		 ((inbits<<3)-1)
95		 /* then, for each byte, shift to the right for each
96		    repetition */
97		 +(((inbits<<3)+13)*(i/inbits))
98		 /* last, pick out the correct byte within that
99		    shifted repetition */
100		 +((inbits-(i%inbits))<<3)
101		 )%(inbits<<3);
102
103	/* pull out the byte value itself */
104	byte += (((in[((inbits-1)-(msbit>>3))%inbits]<<8)|
105		  (in[((inbits)-(msbit>>3))%inbits]))
106		 >>((msbit&7)+1))&0xff;
107
108	/* do the addition */
109	byte += out[i%outbits];
110	out[i%outbits] = byte&0xff;
111
112#if 0
113	printf("msbit[%d] = %d\tbyte = %02x\tsum = %03x\n", i, msbit,
114	       (((in[((inbits-1)-(msbit>>3))%inbits]<<8)|
115		 (in[((inbits)-(msbit>>3))%inbits]))
116		>>((msbit&7)+1))&0xff, byte);
117#endif
118
119	/* keep around the carry bit, if any */
120	byte >>= 8;
121
122#if 0
123	printf("carry=%d\n", byte);
124#endif
125    }
126
127    /* if there's a carry bit left over, add it back in */
128    if (byte) {
129	for (i=outbits-1; i>=0; i--) {
130	    /* do the addition */
131	    byte += out[i];
132	    out[i] = byte&0xff;
133
134	    /* keep around the carry bit, if any */
135	    byte >>= 8;
136	}
137    }
138}
139
140