Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/transport/chttp2/bin_encoder.h"
35 :
36 : #include <string.h>
37 :
38 : #include "src/core/transport/chttp2/huffsyms.h"
39 : #include <grpc/support/log.h>
40 :
41 : static const char alphabet[] =
42 : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
43 :
44 : typedef struct {
45 : gpr_uint16 bits;
46 : gpr_uint8 length;
47 : } b64_huff_sym;
48 :
49 : static const b64_huff_sym huff_alphabet[64] = {{0x21, 6},
50 : {0x5d, 7},
51 : {0x5e, 7},
52 : {0x5f, 7},
53 : {0x60, 7},
54 : {0x61, 7},
55 : {0x62, 7},
56 : {0x63, 7},
57 : {0x64, 7},
58 : {0x65, 7},
59 : {0x66, 7},
60 : {0x67, 7},
61 : {0x68, 7},
62 : {0x69, 7},
63 : {0x6a, 7},
64 : {0x6b, 7},
65 : {0x6c, 7},
66 : {0x6d, 7},
67 : {0x6e, 7},
68 : {0x6f, 7},
69 : {0x70, 7},
70 : {0x71, 7},
71 : {0x72, 7},
72 : {0xfc, 8},
73 : {0x73, 7},
74 : {0xfd, 8},
75 : {0x3, 5},
76 : {0x23, 6},
77 : {0x4, 5},
78 : {0x24, 6},
79 : {0x5, 5},
80 : {0x25, 6},
81 : {0x26, 6},
82 : {0x27, 6},
83 : {0x6, 5},
84 : {0x74, 7},
85 : {0x75, 7},
86 : {0x28, 6},
87 : {0x29, 6},
88 : {0x2a, 6},
89 : {0x7, 5},
90 : {0x2b, 6},
91 : {0x76, 7},
92 : {0x2c, 6},
93 : {0x8, 5},
94 : {0x9, 5},
95 : {0x2d, 6},
96 : {0x77, 7},
97 : {0x78, 7},
98 : {0x79, 7},
99 : {0x7a, 7},
100 : {0x7b, 7},
101 : {0x0, 5},
102 : {0x1, 5},
103 : {0x2, 5},
104 : {0x19, 6},
105 : {0x1a, 6},
106 : {0x1b, 6},
107 : {0x1c, 6},
108 : {0x1d, 6},
109 : {0x1e, 6},
110 : {0x1f, 6},
111 : {0x7fb, 11},
112 : {0x18, 6}};
113 :
114 : static const gpr_uint8 tail_xtra[3] = {0, 2, 3};
115 :
116 23 : gpr_slice grpc_chttp2_base64_encode(gpr_slice input) {
117 23 : size_t input_length = GPR_SLICE_LENGTH(input);
118 23 : size_t input_triplets = input_length / 3;
119 23 : size_t tail_case = input_length % 3;
120 23 : size_t output_length = input_triplets * 4 + tail_xtra[tail_case];
121 23 : gpr_slice output = gpr_slice_malloc(output_length);
122 23 : gpr_uint8 *in = GPR_SLICE_START_PTR(input);
123 23 : char *out = (char *)GPR_SLICE_START_PTR(output);
124 : size_t i;
125 :
126 : /* encode full triplets */
127 152 : for (i = 0; i < input_triplets; i++) {
128 129 : out[0] = alphabet[in[0] >> 2];
129 129 : out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
130 129 : out[2] = alphabet[((in[1] & 0xf) << 2) | (in[2] >> 6)];
131 129 : out[3] = alphabet[in[2] & 0x3f];
132 129 : out += 4;
133 129 : in += 3;
134 : }
135 :
136 : /* encode the remaining bytes */
137 23 : switch (tail_case) {
138 : case 0:
139 9 : break;
140 : case 1:
141 7 : out[0] = alphabet[in[0] >> 2];
142 7 : out[1] = alphabet[(in[0] & 0x3) << 4];
143 7 : out += 2;
144 7 : in += 1;
145 7 : break;
146 : case 2:
147 7 : out[0] = alphabet[in[0] >> 2];
148 7 : out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
149 7 : out[2] = alphabet[(in[1] & 0xf) << 2];
150 7 : out += 3;
151 7 : in += 2;
152 7 : break;
153 : }
154 :
155 23 : GPR_ASSERT(out == (char *)GPR_SLICE_END_PTR(output));
156 23 : GPR_ASSERT(in == GPR_SLICE_END_PTR(input));
157 23 : return output;
158 : }
159 :
160 22 : gpr_slice grpc_chttp2_huffman_compress(gpr_slice input) {
161 : size_t nbits;
162 : gpr_uint8 *in;
163 : gpr_uint8 *out;
164 : gpr_slice output;
165 22 : gpr_uint32 temp = 0;
166 22 : gpr_uint32 temp_length = 0;
167 :
168 22 : nbits = 0;
169 639 : for (in = GPR_SLICE_START_PTR(input); in != GPR_SLICE_END_PTR(input); ++in) {
170 617 : nbits += grpc_chttp2_huffsyms[*in].length;
171 : }
172 :
173 22 : output = gpr_slice_malloc(nbits / 8 + (nbits % 8 != 0));
174 22 : out = GPR_SLICE_START_PTR(output);
175 639 : for (in = GPR_SLICE_START_PTR(input); in != GPR_SLICE_END_PTR(input); ++in) {
176 617 : int sym = *in;
177 617 : temp <<= grpc_chttp2_huffsyms[sym].length;
178 617 : temp |= grpc_chttp2_huffsyms[sym].bits;
179 617 : temp_length += grpc_chttp2_huffsyms[sym].length;
180 :
181 1712 : while (temp_length > 8) {
182 478 : temp_length -= 8;
183 478 : *out++ = (gpr_uint8)(temp >> temp_length);
184 : }
185 : }
186 :
187 22 : if (temp_length) {
188 : /* NB: the following integer arithmetic operation needs to be in its
189 : * expanded form due to the "integral promotion" performed (see section
190 : * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
191 : * is then required to avoid the compiler warning */
192 42 : *out++ = (gpr_uint8)((gpr_uint8)(temp << (8u - temp_length)) |
193 21 : (gpr_uint8)(0xffu >> temp_length));
194 : }
195 :
196 22 : GPR_ASSERT(out == GPR_SLICE_END_PTR(output));
197 :
198 22 : return output;
199 : }
200 :
201 : typedef struct {
202 : gpr_uint32 temp;
203 : gpr_uint32 temp_length;
204 : gpr_uint8 *out;
205 : } huff_out;
206 :
207 1367 : static void enc_flush_some(huff_out *out) {
208 4856 : while (out->temp_length > 8) {
209 2122 : out->temp_length -= 8;
210 2122 : *out->out++ = (gpr_uint8)(out->temp >> out->temp_length);
211 : }
212 1367 : }
213 :
214 1334 : static void enc_add2(huff_out *out, gpr_uint8 a, gpr_uint8 b) {
215 1334 : b64_huff_sym sa = huff_alphabet[a];
216 1334 : b64_huff_sym sb = huff_alphabet[b];
217 4002 : out->temp = (out->temp << (sa.length + sb.length)) |
218 2668 : ((gpr_uint32)sa.bits << sb.length) | sb.bits;
219 1334 : out->temp_length += (gpr_uint32)sa.length + (gpr_uint32)sb.length;
220 1334 : enc_flush_some(out);
221 1334 : }
222 :
223 33 : static void enc_add1(huff_out *out, gpr_uint8 a) {
224 33 : b64_huff_sym sa = huff_alphabet[a];
225 33 : out->temp = (out->temp << sa.length) | sa.bits;
226 33 : out->temp_length += sa.length;
227 33 : enc_flush_some(out);
228 33 : }
229 :
230 127 : gpr_slice grpc_chttp2_base64_encode_and_huffman_compress(gpr_slice input) {
231 127 : size_t input_length = GPR_SLICE_LENGTH(input);
232 127 : size_t input_triplets = input_length / 3;
233 127 : size_t tail_case = input_length % 3;
234 127 : size_t output_syms = input_triplets * 4 + tail_xtra[tail_case];
235 127 : size_t max_output_bits = 11 * output_syms;
236 127 : size_t max_output_length = max_output_bits / 8 + (max_output_bits % 8 != 0);
237 127 : gpr_slice output = gpr_slice_malloc(max_output_length);
238 127 : gpr_uint8 *in = GPR_SLICE_START_PTR(input);
239 127 : gpr_uint8 *start_out = GPR_SLICE_START_PTR(output);
240 : huff_out out;
241 : size_t i;
242 :
243 127 : out.temp = 0;
244 127 : out.temp_length = 0;
245 127 : out.out = start_out;
246 :
247 : /* encode full triplets */
248 747 : for (i = 0; i < input_triplets; i++) {
249 620 : enc_add2(&out, in[0] >> 2, (gpr_uint8)((in[0] & 0x3) << 4) | (in[1] >> 4));
250 620 : enc_add2(&out, (gpr_uint8)((in[1] & 0xf) << 2) | (in[2] >> 6),
251 620 : (gpr_uint8)(in[2] & 0x3f));
252 620 : in += 3;
253 : }
254 :
255 : /* encode the remaining bytes */
256 127 : switch (tail_case) {
257 : case 0:
258 33 : break;
259 : case 1:
260 61 : enc_add2(&out, in[0] >> 2, (gpr_uint8)((in[0] & 0x3) << 4));
261 61 : in += 1;
262 61 : break;
263 : case 2:
264 33 : enc_add2(&out, in[0] >> 2,
265 33 : (gpr_uint8)((in[0] & 0x3) << 4) | (gpr_uint8)(in[1] >> 4));
266 33 : enc_add1(&out, (gpr_uint8)((in[1] & 0xf) << 2));
267 33 : in += 2;
268 33 : break;
269 : }
270 :
271 127 : if (out.temp_length) {
272 : /* NB: the following integer arithmetic operation needs to be in its
273 : * expanded form due to the "integral promotion" performed (see section
274 : * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
275 : * is then required to avoid the compiler warning */
276 252 : *out.out++ = (gpr_uint8)((gpr_uint8)(out.temp << (8u - out.temp_length)) |
277 126 : (gpr_uint8)(0xffu >> out.temp_length));
278 : }
279 :
280 127 : GPR_ASSERT(out.out <= GPR_SLICE_END_PTR(output));
281 127 : GPR_SLICE_SET_LENGTH(output, out.out - start_out);
282 :
283 127 : GPR_ASSERT(in == GPR_SLICE_END_PTR(input));
284 127 : return output;
285 : }
286 :
287 276419 : int grpc_is_binary_header(const char *key, size_t length) {
288 276419 : if (length < 5) return 0;
289 174170 : return 0 == memcmp(key + length - 4, "-bin", 4);
290 : }
|
