Import of code from heimdal
[openafs.git] / src / external / heimdal / krb5 / n-fold.c
1 /*
2  * Copyright (c) 1999 Kungliga Tekniska Högskolan
3  * (Royal Institute of Technology, Stockholm, Sweden).
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  *
17  * 3. Neither the name of KTH nor the names of its contributors may be
18  *    used to endorse or promote products derived from this software without
19  *    specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY KTH AND ITS CONTRIBUTORS ``AS IS'' AND ANY
22  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL KTH OR ITS CONTRIBUTORS BE
25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
28  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
32
33 #include "krb5_locl.h"
34
35 static void
36 rr13(uint8_t *dst1, uint8_t *dst2, uint8_t *src, size_t len)
37 {
38     int bytes = (len + 7) / 8;
39     int i;
40     const int bits = 13 % len;
41
42     for (i = 0; i < bytes; i++) {
43         int bb;
44         int b1, s1, b2, s2;
45         /* calculate first bit position of this byte */
46         bb = 8 * i - bits;
47         while(bb < 0)
48             bb += len;
49         /* byte offset and shift count */
50         b1 = bb / 8;
51         s1 = bb % 8;
52
53         if (bb + 8 > bytes * 8)
54             /* watch for wraparound */
55             s2 = (len + 8 - s1) % 8;
56         else
57             s2 = 8 - s1;
58         b2 = (b1 + 1) % bytes;
59         dst1[i] = (src[b1] << s1) | (src[b2] >> s2);
60         dst2[i] = dst1[i];
61     }
62
63     return;
64 }
65
66 /*
67  * Add `b' to `a', both being one's complement numbers.
68  * This function assumes that inputs *a, *b are aligned
69  * to 4 bytes.
70  */
71 static void
72 add1(uint8_t *a, uint8_t *b, size_t len)
73 {
74     int i;
75     int carry = 0;
76     uint32_t x;
77     uint32_t left, right;
78
79     for (i = len - 1; (i+1) % 4; i--) {
80         x = a[i] + b[i] + carry;
81         carry = x > 0xff;
82         a[i] = x & 0xff;
83     }
84
85     for (i = len / 4 - 1; i >= 0; i--) {
86         left = ntohl(((uint32_t *)a)[i]);
87         right = ntohl(((uint32_t *)b)[i]);
88         x = left + right + carry;
89         carry = x < left || x < right;
90         ((uint32_t *)a)[i]  = x;
91     }
92
93     for (i = len - 1; (i+1) % 4; i--) {
94         x = a[i] + carry;
95         carry = x > 0xff;
96         a[i] = x & 0xff;
97     }
98
99     for (i = len / 4 - 1; carry && i >= 0; i--) {
100         left = ((uint32_t *)a)[i];
101         x = left + carry;
102         carry = x < left;
103         ((uint32_t *)a)[i] = x;
104     }
105
106     for (i = len / 4 - 1; i >=0; i--)
107         ((uint32_t *)a)[i] = htonl(((uint32_t *)a)[i]);
108 }
109
110 KRB5_LIB_FUNCTION krb5_error_code KRB5_LIB_CALL
111 _krb5_n_fold(const void *str, size_t len, void *key, size_t size)
112 {
113     /* if len < size we need at most N * len bytes, ie < 2 * size;
114        if len > size we need at most 2 * len */
115     size_t maxlen = 2 * max(size, len);
116     size_t l = 0;
117     uint8_t *tmp;
118     uint8_t *tmpbuf;
119     uint8_t *buf1;
120     uint8_t *buf2;
121
122     tmp = malloc(maxlen + 2 * len);
123     if (tmp == NULL)
124         return ENOMEM;
125
126     buf1 = tmp + maxlen;
127     buf2 = tmp + maxlen + len;
128
129     memset(key, 0, size);
130     memcpy(buf1, str, len);
131     memcpy(tmp, buf1, len);
132     do {
133         l += len;
134         while(l >= size) {
135             add1(key, tmp, size);
136             l -= size;
137             if(l == 0)
138                 break;
139             memmove(tmp, tmp + size, l);
140         }
141         rr13(tmp + l, buf2, buf1, len * 8);
142         tmpbuf = buf1;
143         buf1 = buf2;
144         buf2 = tmpbuf;
145     } while(l != 0);
146
147     memset(tmp, 0, maxlen + 2 * len);
148     free(tmp);
149     return 0;
150 }