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