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