hare

[hare] The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

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 };