encoding.ha (8933B)
1 // SPDX-License-Identifier: MPL-2.0 2 // (c) Hare authors <https://harelang.org> 3 4 // The following code was initially ported from BearSSL. 5 // 6 // Copyright (c) 2017 Thomas Pornin <pornin@bolet.org> 7 // 8 // Permission is hereby granted, free of charge, to any person obtaining a copy 9 // of this software and associated documentation files (the "Software"), to deal 10 // in the Software without restriction, including without limitation the rights 11 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 12 // copies of the Software, and to permit persons to whom the Software is 13 // furnished to do so, subject to the following conditions: 14 // 15 // The above copyright notice and this permission notice shall be included in 16 // all copies or substantial portions of the Software. 17 // 18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 23 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 24 // SOFTWARE. 25 use crypto::math::*; 26 27 // Minimal required words to encode 'x' into an []word. To statically allocate 28 // resources, following expression may be used: 29 // 30 // ((number_of_bits + WORD_BITSZ - 1) / WORD_BITSZ) + 1 31 export fn encodelen(x: []u8) size = { 32 return (((len(x) * 8) + WORD_BITSZ - 1) / WORD_BITSZ) + 1; 33 }; 34 35 // Encode 'src' from its big-endian unsigned encoding into the internal 36 // representation. The caller must make sure that 'dest' has enough space to 37 // store 'src'. See [[encodelen]] for how to calculate the required size. 38 // 39 // This function runs in constant time for given 'src' length. 40 export fn encode(dest: []word, src: const []u8) void = { 41 let acc: u32 = 0; 42 let accbits: u32 = 0; 43 let didx: size = 1; 44 45 for (let i = len(src) - 1; i < len(src); i -= 1) { 46 acc |= (src[i] << accbits); 47 accbits += 8; 48 49 if (accbits >= WORD_BITSZ) { 50 dest[didx] = (acc & WORD_BITMASK): word; 51 accbits -= WORD_BITSZ; 52 acc = src[i] >> (8 - accbits); 53 didx += 1; 54 }; 55 }; 56 57 dest[didx] = acc: word; 58 59 dest[0] = countbits(dest[1..didx + 1]): word; 60 }; 61 62 // Get the announced bit length of 'n' in encoded form. 63 fn countbits(n: const []word) u32 = { 64 let tw: u32 = 0; 65 let twk: u32 = 0; 66 67 for (let i = len(n) - 1; i < len(n); i -= 1) { 68 const c = equ32(tw, 0); 69 const w = n[i]; 70 tw = muxu32(c, w, tw); 71 twk = muxu32(c, i: u32, twk); 72 }; 73 74 return (twk << WORD_SHIFT) + word_countbits(tw); 75 }; 76 77 // Counts the number of bits until including the highest bit set to 1. 78 fn word_countbits(x: u32) u32 = { 79 let k: u32 = nequ32(x, 0); 80 let c: u32 = 0; 81 82 c = gtu32(x, 0xffff); 83 x = muxu32(c, x >> 16, x); 84 k += c << 4; 85 86 c = gtu32(x, 0x00ff); 87 x = muxu32(c, x >> 8, x); 88 k += c << 3; 89 90 c = gtu32(x, 0x000f); 91 x = muxu32(c, x >> 4, x); 92 k += c << 2; 93 94 c = gtu32(x, 0x0003); 95 x = muxu32(c, x >> 2, x); 96 k += c << 1; 97 98 k += gtu32(x, 0x0001); 99 100 return k; 101 }; 102 103 // Get the encoded bit length of a word. 104 fn ebitlen(x: const []word) u32 = { 105 return x[0]; 106 }; 107 108 // Get the effective word lenght of 'x'. The effective wordlen is the number of 109 // words that are used to represent the actual value. Eg. the number 7 will have 110 // an effective word length of 1, no matter of len(x). The first element 111 // containing the encoded word len is not added to the result. 112 export fn ewordlen(x: const []word) u32 = { 113 return (x[0] + WORD_BITSZ) >> WORD_SHIFT; 114 }; 115 116 // Decode 'src' into a big-endian unsigned byte array. The caller must ensure 117 // that 'dest' has enough space to store the decoded value. See [[decodelen]] on 118 // how to determine the required length. 119 export fn decode(dest: []u8, src: const []word) void = { 120 let acc: u64 = 0; 121 let accbits: u64 = 0; 122 let sidx: size = 1; 123 let sz = ewordlen(src); 124 for (let i = len(dest) - 1; i < len(dest); i -= 1) { 125 if (accbits < 8) { 126 if (sidx <= sz) { 127 acc |= ((src[sidx]: u64) << accbits: u64): u64; 128 sidx += 1; 129 }; 130 accbits += WORD_BITSZ; 131 }; 132 dest[i] = acc: u8; 133 acc >>= 8; 134 accbits -= 8; 135 }; 136 }; 137 138 // Returns the number of bytes required to store a big integer given by 'src'. 139 // 140 // For static allocation following expression may be used: 141 // 142 // ((len(src) - 1) * WORD_BITSZ + 7) / 8 143 export fn decodelen(src: const []word) size = { 144 return ((len(src) - 1) * WORD_BITSZ + 7) / 8; 145 }; 146 147 // Encodes an integer from its big-endian unsigned encoding. 'src' must be lower 148 // than 'm'. If not 'dest' will be set to 0. 'dest' will have the announced bit 149 // length of 'm' after decoding. 150 // 151 // The return value is 1 if the decoded value fits within 'm' or 0 otherwise. 152 // 153 // This function runs in constant time for a given 'src' length and announced 154 // bit length of m, independent of whether the value fits within 'm' or not. 155 export fn encodemod(dest: []word, src: const []u8, m: const []word) u32 = { 156 // Two-pass algorithm: in the first pass, we determine whether the 157 // value fits; in the second pass, we do the actual write. 158 // 159 // During the first pass, 'r' contains the comparison result so 160 // far: 161 // 0x00000000 value is equal to the modulus 162 // 0x00000001 value is greater than the modulus 163 // 0xFFFFFFFF value is lower than the modulus 164 // 165 // Since we iterate starting with the least significant bytes (at 166 // the end of src[]), each new comparison overrides the previous 167 // except when the comparison yields 0 (equal). 168 // 169 // During the second pass, 'r' is either 0xFFFFFFFF (value fits) 170 // or 0x00000000 (value does not fit). 171 // 172 // We must iterate over all bytes of the source, _and_ possibly 173 // some extra virtual bytes (with value 0) so as to cover the 174 // complete modulus as well. We also add 4 such extra bytes beyond 175 // the modulus length because it then guarantees that no accumulated 176 // partial word remains to be processed. 177 178 let mlen = 0z, tlen = 0z; 179 180 mlen = ewordlen(m); 181 tlen = mlen << (WORD_SHIFT - 3); // mlen in bytes 182 if (tlen < len(src)) { 183 tlen = len(src); 184 }; 185 tlen += 4; 186 let r: u32 = 0; 187 for (let pass = 0z; pass < 2; pass += 1) { 188 let v: size = 1; 189 let acc: u32 = 0, acc_len: u32 = 0; 190 191 for (let u = 0z; u < tlen; u += 1) { 192 // inner loop is similar to encode until the mlen check 193 let b: u32 = 0; 194 195 if (u < len(src)) { 196 b = src[len(src) - 1 - u]; 197 }; 198 acc |= (b << acc_len); 199 acc_len += 8; 200 if (acc_len >= WORD_BITSZ) { 201 const xw: u32 = acc & WORD_BITMASK; 202 acc_len -= WORD_BITSZ; 203 acc = b >> (8 - acc_len); 204 if (v <= mlen) { 205 if (pass == 1) { 206 dest[v] = (r & xw): word; 207 } else { 208 let cc = cmpu32(xw, m[v]: u32): u32; 209 r = muxu32(equ32(cc, 0), r, cc); 210 }; 211 } else { 212 if (pass == 0) { 213 r = muxu32(equ32(xw, 0), r, 1); 214 }; 215 }; 216 v += 1; 217 }; 218 }; 219 220 // When we reach this point at the end of the first pass: 221 // r is either 0, 1 or -1; we want to set r to 0 if it 222 // is equal to 0 or 1, and leave it to -1 otherwise. 223 // 224 // When we reach this point at the end of the second pass: 225 // r is either 0 or -1; we want to leave that value 226 // untouched. This is a subcase of the previous. 227 r >>= 1; 228 r |= (r << 1); 229 }; 230 231 dest[0] = m[0]; 232 return r & 1; 233 }; 234 235 // Encode an integer from its big-endian unsigned representation, and reduce it 236 // modulo the provided modulus 'm'. The announced bit length of the result is 237 // set to be equal to that of the modulus. 238 // 239 // 'dest' must be distinct from 'm'. 240 export fn encodereduce(dest: []word, src: const []u8, m: const []word) void = { 241 assert(&dest[0] != &m[0], "'dest' and 'm' must be distinct"); 242 243 // Get the encoded bit length. 244 const m_ebitlen = m[0]; 245 246 // Special case for an invalid (null) modulus. 247 if (m_ebitlen == 0) { 248 dest[0] = 0; 249 return; 250 }; 251 252 zero(dest, m_ebitlen); 253 254 // First decode directly as many bytes as possible. This requires 255 // computing the actual bit length. 256 let m_rbitlen = m_ebitlen >> WORD_SHIFT; 257 m_rbitlen = (m_ebitlen & WORD_BITSZ) 258 + (m_rbitlen << WORD_SHIFT) - m_rbitlen; 259 const mblen: size = (m_rbitlen + 7) >> 3; 260 let k: size = mblen - 1; 261 if (k >= len(src)) { 262 encode(dest, src); 263 dest[0] = m_ebitlen; 264 return; 265 }; 266 encode(dest, src[..k]); 267 dest[0] = m_ebitlen; 268 269 // Input remaining bytes, using 31-bit words. 270 let acc: word = 0; 271 let acc_len: word = 0; 272 for (k < len(src)) { 273 const v = src[k]; 274 k += 1; 275 if (acc_len >= 23) { 276 acc_len -= 23; 277 acc <<= (8 - acc_len); 278 acc |= v >> acc_len; 279 muladd_small(dest, acc, m); 280 acc = v & (0xFF >> (8 - acc_len)); 281 } else { 282 acc = (acc << 8) | v; 283 acc_len += 8; 284 }; 285 }; 286 287 // We may have some bits accumulated. We then perform a shift to 288 // be able to inject these bits as a full 31-bit word. 289 if (acc_len != 0) { 290 acc = (acc | (dest[1] << acc_len)) & WORD_BITMASK; 291 rshift(dest, WORD_BITSZ - acc_len); 292 muladd_small(dest, acc, m); 293 }; 294 };