1 #include "parameters.h"
2 #include "reed_muller.h"
3 #include <stdint.h>
4 #include <string.h>
5 /**
6 * @file reed_muller.c
7 * Constant time implementation of Reed-Muller code RM(1,7)
8 */
9
10
11
12 // number of repeated code words
13 #define MULTIPLICITY CEIL_DIVIDE(PARAM_N2, 128)
14
15 // copy bit 0 into all bits of a 32 bit value
16 #define BIT0MASK(x) (-((x) & 1))
17
18
19 static void encode(uint8_t *word, uint8_t message);
20 static void hadamard(uint16_t src[128], uint16_t dst[128]);
21 static void expand_and_sum(uint16_t dest[128], const uint8_t src[16 * MULTIPLICITY]);
22 static uint8_t find_peaks(const uint16_t transform[128]);
23
24
25
26 /**
27 * @brief Encode a single byte into a single codeword using RM(1,7)
28 *
29 * Encoding matrix of this code:
30 * bit pattern (note that bits are numbered big endian)
31 * 0 aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa
32 * 1 cccccccc cccccccc cccccccc cccccccc
33 * 2 f0f0f0f0 f0f0f0f0 f0f0f0f0 f0f0f0f0
34 * 3 ff00ff00 ff00ff00 ff00ff00 ff00ff00
35 * 4 ffff0000 ffff0000 ffff0000 ffff0000
36 * 5 ffffffff 00000000 ffffffff 00000000
37 * 6 ffffffff ffffffff 00000000 00000000
38 * 7 ffffffff ffffffff ffffffff ffffffff
39 *
40 * @param[out] word An RM(1,7) codeword
41 * @param[in] message A message
42 */
encode(uint8_t * word,uint8_t message)43 static void encode(uint8_t *word, uint8_t message) {
44 uint32_t e;
45 // bit 7 flips all the bits, do that first to save work
46 e = BIT0MASK(message >> 7);
47 // bits 0, 1, 2, 3, 4 are the same for all four longs
48 // (Warning: in the bit matrix above, low bits are at the left!)
49 e ^= BIT0MASK(message >> 0) & 0xaaaaaaaa;
50 e ^= BIT0MASK(message >> 1) & 0xcccccccc;
51 e ^= BIT0MASK(message >> 2) & 0xf0f0f0f0;
52 e ^= BIT0MASK(message >> 3) & 0xff00ff00;
53 e ^= BIT0MASK(message >> 4) & 0xffff0000;
54 // we can store this in the first quarter
55 word[0 + 0] = (e >> 0x00) & 0xff;
56 word[0 + 1] = (e >> 0x08) & 0xff;
57 word[0 + 2] = (e >> 0x10) & 0xff;
58 word[0 + 3] = (e >> 0x18) & 0xff;
59 // bit 5 flips entries 1 and 3; bit 6 flips 2 and 3
60 e ^= BIT0MASK(message >> 5);
61 word[4 + 0] = (e >> 0x00) & 0xff;
62 word[4 + 1] = (e >> 0x08) & 0xff;
63 word[4 + 2] = (e >> 0x10) & 0xff;
64 word[4 + 3] = (e >> 0x18) & 0xff;
65 e ^= BIT0MASK(message >> 6);
66 word[12 + 0] = (e >> 0x00) & 0xff;
67 word[12 + 1] = (e >> 0x08) & 0xff;
68 word[12 + 2] = (e >> 0x10) & 0xff;
69 word[12 + 3] = (e >> 0x18) & 0xff;
70 e ^= BIT0MASK(message >> 5);
71 word[8 + 0] = (e >> 0x00) & 0xff;
72 word[8 + 1] = (e >> 0x08) & 0xff;
73 word[8 + 2] = (e >> 0x10) & 0xff;
74 word[8 + 3] = (e >> 0x18) & 0xff;
75 }
76
77
78
79 /**
80 * @brief Hadamard transform
81 *
82 * Perform hadamard transform of src and store result in dst
83 * src is overwritten: it is also used as intermediate buffer
84 * Method is best explained if we use H(3) instead of H(7):
85 *
86 * The routine multiplies by the matrix H(3):
87 * [1 1 1 1 1 1 1 1]
88 * [1 -1 1 -1 1 -1 1 -1]
89 * [1 1 -1 -1 1 1 -1 -1]
90 * [a b c d e f g h] * [1 -1 -1 1 1 -1 -1 1] = result of routine
91 * [1 1 1 1 -1 -1 -1 -1]
92 * [1 -1 1 -1 -1 1 -1 1]
93 * [1 1 -1 -1 -1 -1 1 1]
94 * [1 -1 -1 1 -1 1 1 -1]
95 * You can do this in three passes, where each pass does this:
96 * set lower half of buffer to pairwise sums,
97 * and upper half to differences
98 * index 0 1 2 3 4 5 6 7
99 * input: a, b, c, d, e, f, g, h
100 * pass 1: a+b, c+d, e+f, g+h, a-b, c-d, e-f, g-h
101 * pass 2: a+b+c+d, e+f+g+h, a-b+c-d, e-f+g-h, a+b-c-d, e+f-g-h, a-b-c+d, e-f-g+h
102 * pass 3: a+b+c+d+e+f+g+h a+b-c-d+e+f-g-h a+b+c+d-e-f-g-h a+b-c-d-e+-f+g+h
103 * a-b+c-d+e-f+g-h a-b-c+d+e-f-g+h a-b+c-d-e+f-g+h a-b-c+d-e+f+g-h
104 * This order of computation is chosen because it vectorises well.
105 * Likewise, this routine multiplies by H(7) in seven passes.
106 *
107 * @param[out] src Structure that contain the expanded codeword
108 * @param[out] dst Structure that contain the expanded codeword
109 */
hadamard(uint16_t src[128],uint16_t dst[128])110 static void hadamard(uint16_t src[128], uint16_t dst[128]) {
111 // the passes move data:
112 // src -> dst -> src -> dst -> src -> dst -> src -> dst
113 // using p1 and p2 alternately
114 uint16_t *p1 = src;
115 uint16_t *p2 = dst;
116 uint16_t *p3;
117 for (uint32_t pass = 0; pass < 7; pass++) {
118 for (uint32_t i = 0; i < 64; i++) {
119 p2[i] = p1[2 * i] + p1[2 * i + 1];
120 p2[i + 64] = p1[2 * i] - p1[2 * i + 1];
121 }
122 // swap p1, p2 for next round
123 p3 = p1;
124 p1 = p2;
125 p2 = p3;
126 }
127 }
128
129
130
131 /**
132 * @brief Add multiple codewords into expanded codeword
133 *
134 * Accesses memory in order
135 * Note: this does not write the codewords as -1 or +1 as the green machine does
136 * instead, just 0 and 1 is used.
137 * The resulting hadamard transform has:
138 * all values are halved
139 * the first entry is 64 too high
140 *
141 * @param[out] dest Structure that contain the expanded codeword
142 * @param[in] src Structure that contain the codeword
143 */
expand_and_sum(uint16_t dest[128],const uint8_t src[16* MULTIPLICITY])144 static void expand_and_sum(uint16_t dest[128], const uint8_t src[16 * MULTIPLICITY]) {
145 size_t part, bit, copy;
146 // start with the first copy
147 for (part = 0; part < 16; part++) {
148 for (bit = 0; bit < 8; bit++) {
149 dest[part * 8 + bit] = (uint16_t) ((src[part] >> bit) & 1);
150 }
151 }
152 // sum the rest of the copies
153 for (copy = 1; copy < MULTIPLICITY; copy++) {
154 for (part = 0; part < 16; part++) {
155 for (bit = 0; bit < 8; bit++) {
156 dest[part * 8 + bit] += (uint16_t) ((src[16 * copy + part] >> bit) & 1);
157 }
158 }
159 }
160 }
161
162
163
164 /**
165 * @brief Finding the location of the highest value
166 *
167 * This is the final step of the green machine: find the location of the highest value,
168 * and add 128 if the peak is positive
169 * if there are two identical peaks, the peak with smallest value
170 * in the lowest 7 bits it taken
171 * @param[in] transform Structure that contain the expanded codeword
172 */
find_peaks(const uint16_t transform[128])173 static uint8_t find_peaks(const uint16_t transform[128]) {
174 uint16_t peak_abs = 0;
175 uint16_t peak = 0;
176 uint16_t pos = 0;
177 uint16_t t, abs, mask;
178 for (uint16_t i = 0; i < 128; i++) {
179 t = transform[i];
180 abs = t ^ ((-(t >> 15)) & (t ^ -t)); // t = abs(t)
181 mask = -(((uint16_t)(peak_abs - abs)) >> 15);
182 peak ^= mask & (peak ^ t);
183 pos ^= mask & (pos ^ i);
184 peak_abs ^= mask & (peak_abs ^ abs);
185 }
186 pos |= 128 & ((peak >> 15) - 1);
187 return (uint8_t) pos;
188 }
189
190
191
192
193 /**
194 * @brief Encodes the received word
195 *
196 * The message consists of N1 bytes each byte is encoded into PARAM_N2 bits,
197 * or MULTIPLICITY repeats of 128 bits
198 *
199 * @param[out] cdw Array of size VEC_N1N2_SIZE_64 receiving the encoded message
200 * @param[in] msg Array of size VEC_N1_SIZE_64 storing the message
201 */
PQCLEAN_HQCRMRS192_CLEAN_reed_muller_encode(uint8_t * cdw,const uint8_t * msg)202 void PQCLEAN_HQCRMRS192_CLEAN_reed_muller_encode(uint8_t *cdw, const uint8_t *msg) {
203 for (size_t i = 0; i < VEC_N1_SIZE_BYTES; i++) {
204 // encode first word
205 encode(&cdw[16 * i * MULTIPLICITY], msg[i]);
206 // copy to other identical codewords
207 for (size_t copy = 1; copy < MULTIPLICITY; copy++) {
208 memcpy(&cdw[16 * i * MULTIPLICITY + 16 * copy], &cdw[16 * i * MULTIPLICITY], 16);
209 }
210 }
211 }
212
213
214
215 /**
216 * @brief Decodes the received word
217 *
218 * Decoding uses fast hadamard transform, for a more complete picture on Reed-Muller decoding, see MacWilliams, Florence Jessie, and Neil James Alexander Sloane.
219 * The theory of error-correcting codes codes @cite macwilliams1977theory
220 *
221 * @param[out] msg Array of size VEC_N1_SIZE_64 receiving the decoded message
222 * @param[in] cdw Array of size VEC_N1N2_SIZE_64 storing the received word
223 */
PQCLEAN_HQCRMRS192_CLEAN_reed_muller_decode(uint8_t * msg,const uint8_t * cdw)224 void PQCLEAN_HQCRMRS192_CLEAN_reed_muller_decode(uint8_t *msg, const uint8_t *cdw) {
225 uint16_t expanded[128];
226 uint16_t transform[128];
227 for (size_t i = 0; i < VEC_N1_SIZE_BYTES; i++) {
228 // collect the codewords
229 expand_and_sum(expanded, &cdw[16 * i * MULTIPLICITY]);
230 // apply hadamard transform
231 hadamard(expanded, transform);
232 // fix the first entry to get the half Hadamard transform
233 transform[0] -= 64 * MULTIPLICITY;
234 // finish the decoding
235 msg[i] = find_peaks(transform);
236 }
237 }
238