1 /* 2 * Copyright (c) 2017 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_i15_decode_reduce(uint16_t *x, 30 const void *src, size_t len, const uint16_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_i15_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 >> 4; 61 m_rbitlen = (m_ebitlen & 15) + (m_rbitlen << 4) - m_rbitlen; 62 mblen = (m_rbitlen + 7) >> 3; 63 k = mblen - 1; 64 if (k >= len) { 65 br_i15_decode(x, src, len); 66 x[0] = m_ebitlen; 67 return; 68 } 69 buf = src; 70 br_i15_decode(x, buf, k); 71 x[0] = m_ebitlen; 72 73 /* 74 * Input remaining bytes, using 15-bit words. 75 */ 76 acc = 0; 77 acc_len = 0; 78 while (k < len) { 79 uint32_t v; 80 81 v = buf[k ++]; 82 acc = (acc << 8) | v; 83 acc_len += 8; 84 if (acc_len >= 15) { 85 br_i15_muladd_small(x, acc >> (acc_len - 15), m); 86 acc_len -= 15; 87 acc &= ~((uint32_t)-1 << acc_len); 88 } 89 } 90 91 /* 92 * We may have some bits accumulated. We then perform a shift to 93 * be able to inject these bits as a full 15-bit word. 94 */ 95 if (acc_len != 0) { 96 acc = (acc | (x[1] << acc_len)) & 0x7FFF; 97 br_i15_rshift(x, 15 - acc_len); 98 br_i15_muladd_small(x, acc, m); 99 } 100 } 101