1*0957b409SSimon J. Gerraty /*
2*0957b409SSimon J. Gerraty * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3*0957b409SSimon J. Gerraty *
4*0957b409SSimon J. Gerraty * Permission is hereby granted, free of charge, to any person obtaining
5*0957b409SSimon J. Gerraty * a copy of this software and associated documentation files (the
6*0957b409SSimon J. Gerraty * "Software"), to deal in the Software without restriction, including
7*0957b409SSimon J. Gerraty * without limitation the rights to use, copy, modify, merge, publish,
8*0957b409SSimon J. Gerraty * distribute, sublicense, and/or sell copies of the Software, and to
9*0957b409SSimon J. Gerraty * permit persons to whom the Software is furnished to do so, subject to
10*0957b409SSimon J. Gerraty * the following conditions:
11*0957b409SSimon J. Gerraty *
12*0957b409SSimon J. Gerraty * The above copyright notice and this permission notice shall be
13*0957b409SSimon J. Gerraty * included in all copies or substantial portions of the Software.
14*0957b409SSimon J. Gerraty *
15*0957b409SSimon J. Gerraty * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16*0957b409SSimon J. Gerraty * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17*0957b409SSimon J. Gerraty * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18*0957b409SSimon J. Gerraty * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19*0957b409SSimon J. Gerraty * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20*0957b409SSimon J. Gerraty * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21*0957b409SSimon J. Gerraty * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22*0957b409SSimon J. Gerraty * SOFTWARE.
23*0957b409SSimon J. Gerraty */
24*0957b409SSimon J. Gerraty
25*0957b409SSimon J. Gerraty #include "inner.h"
26*0957b409SSimon J. Gerraty
27*0957b409SSimon J. Gerraty /* see inner.h */
28*0957b409SSimon J. Gerraty void
br_i31_decode_reduce(uint32_t * x,const void * src,size_t len,const uint32_t * m)29*0957b409SSimon J. Gerraty br_i31_decode_reduce(uint32_t *x,
30*0957b409SSimon J. Gerraty const void *src, size_t len, const uint32_t *m)
31*0957b409SSimon J. Gerraty {
32*0957b409SSimon J. Gerraty uint32_t m_ebitlen, m_rbitlen;
33*0957b409SSimon J. Gerraty size_t mblen, k;
34*0957b409SSimon J. Gerraty const unsigned char *buf;
35*0957b409SSimon J. Gerraty uint32_t acc;
36*0957b409SSimon J. Gerraty int acc_len;
37*0957b409SSimon J. Gerraty
38*0957b409SSimon J. Gerraty /*
39*0957b409SSimon J. Gerraty * Get the encoded bit length.
40*0957b409SSimon J. Gerraty */
41*0957b409SSimon J. Gerraty m_ebitlen = m[0];
42*0957b409SSimon J. Gerraty
43*0957b409SSimon J. Gerraty /*
44*0957b409SSimon J. Gerraty * Special case for an invalid (null) modulus.
45*0957b409SSimon J. Gerraty */
46*0957b409SSimon J. Gerraty if (m_ebitlen == 0) {
47*0957b409SSimon J. Gerraty x[0] = 0;
48*0957b409SSimon J. Gerraty return;
49*0957b409SSimon J. Gerraty }
50*0957b409SSimon J. Gerraty
51*0957b409SSimon J. Gerraty /*
52*0957b409SSimon J. Gerraty * Clear the destination.
53*0957b409SSimon J. Gerraty */
54*0957b409SSimon J. Gerraty br_i31_zero(x, m_ebitlen);
55*0957b409SSimon J. Gerraty
56*0957b409SSimon J. Gerraty /*
57*0957b409SSimon J. Gerraty * First decode directly as many bytes as possible. This requires
58*0957b409SSimon J. Gerraty * computing the actual bit length.
59*0957b409SSimon J. Gerraty */
60*0957b409SSimon J. Gerraty m_rbitlen = m_ebitlen >> 5;
61*0957b409SSimon J. Gerraty m_rbitlen = (m_ebitlen & 31) + (m_rbitlen << 5) - m_rbitlen;
62*0957b409SSimon J. Gerraty mblen = (m_rbitlen + 7) >> 3;
63*0957b409SSimon J. Gerraty k = mblen - 1;
64*0957b409SSimon J. Gerraty if (k >= len) {
65*0957b409SSimon J. Gerraty br_i31_decode(x, src, len);
66*0957b409SSimon J. Gerraty x[0] = m_ebitlen;
67*0957b409SSimon J. Gerraty return;
68*0957b409SSimon J. Gerraty }
69*0957b409SSimon J. Gerraty buf = src;
70*0957b409SSimon J. Gerraty br_i31_decode(x, buf, k);
71*0957b409SSimon J. Gerraty x[0] = m_ebitlen;
72*0957b409SSimon J. Gerraty
73*0957b409SSimon J. Gerraty /*
74*0957b409SSimon J. Gerraty * Input remaining bytes, using 31-bit words.
75*0957b409SSimon J. Gerraty */
76*0957b409SSimon J. Gerraty acc = 0;
77*0957b409SSimon J. Gerraty acc_len = 0;
78*0957b409SSimon J. Gerraty while (k < len) {
79*0957b409SSimon J. Gerraty uint32_t v;
80*0957b409SSimon J. Gerraty
81*0957b409SSimon J. Gerraty v = buf[k ++];
82*0957b409SSimon J. Gerraty if (acc_len >= 23) {
83*0957b409SSimon J. Gerraty acc_len -= 23;
84*0957b409SSimon J. Gerraty acc <<= (8 - acc_len);
85*0957b409SSimon J. Gerraty acc |= v >> acc_len;
86*0957b409SSimon J. Gerraty br_i31_muladd_small(x, acc, m);
87*0957b409SSimon J. Gerraty acc = v & (0xFF >> (8 - acc_len));
88*0957b409SSimon J. Gerraty } else {
89*0957b409SSimon J. Gerraty acc = (acc << 8) | v;
90*0957b409SSimon J. Gerraty acc_len += 8;
91*0957b409SSimon J. Gerraty }
92*0957b409SSimon J. Gerraty }
93*0957b409SSimon J. Gerraty
94*0957b409SSimon J. Gerraty /*
95*0957b409SSimon J. Gerraty * We may have some bits accumulated. We then perform a shift to
96*0957b409SSimon J. Gerraty * be able to inject these bits as a full 31-bit word.
97*0957b409SSimon J. Gerraty */
98*0957b409SSimon J. Gerraty if (acc_len != 0) {
99*0957b409SSimon J. Gerraty acc = (acc | (x[1] << acc_len)) & 0x7FFFFFFF;
100*0957b409SSimon J. Gerraty br_i31_rshift(x, 31 - acc_len);
101*0957b409SSimon J. Gerraty br_i31_muladd_small(x, acc, m);
102*0957b409SSimon J. Gerraty }
103*0957b409SSimon J. Gerraty }
104