1 //
2 //
3 // Copyright 2015 gRPC authors.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 //
18
19 #include "src/core/ext/transport/chttp2/transport/bin_encoder.h"
20
21 #include <grpc/support/port_platform.h>
22 #include <stdint.h>
23 #include <string.h>
24
25 #include "absl/log/check.h"
26 #include "src/core/ext/transport/chttp2/transport/huffsyms.h"
27
28 static const char alphabet[] =
29 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
30
31 struct b64_huff_sym {
32 uint16_t bits;
33 uint8_t length;
34 };
35 static const b64_huff_sym huff_alphabet[64] = {
36 {0x21, 6}, {0x5d, 7}, {0x5e, 7}, {0x5f, 7}, {0x60, 7}, {0x61, 7},
37 {0x62, 7}, {0x63, 7}, {0x64, 7}, {0x65, 7}, {0x66, 7}, {0x67, 7},
38 {0x68, 7}, {0x69, 7}, {0x6a, 7}, {0x6b, 7}, {0x6c, 7}, {0x6d, 7},
39 {0x6e, 7}, {0x6f, 7}, {0x70, 7}, {0x71, 7}, {0x72, 7}, {0xfc, 8},
40 {0x73, 7}, {0xfd, 8}, {0x3, 5}, {0x23, 6}, {0x4, 5}, {0x24, 6},
41 {0x5, 5}, {0x25, 6}, {0x26, 6}, {0x27, 6}, {0x6, 5}, {0x74, 7},
42 {0x75, 7}, {0x28, 6}, {0x29, 6}, {0x2a, 6}, {0x7, 5}, {0x2b, 6},
43 {0x76, 7}, {0x2c, 6}, {0x8, 5}, {0x9, 5}, {0x2d, 6}, {0x77, 7},
44 {0x78, 7}, {0x79, 7}, {0x7a, 7}, {0x7b, 7}, {0x0, 5}, {0x1, 5},
45 {0x2, 5}, {0x19, 6}, {0x1a, 6}, {0x1b, 6}, {0x1c, 6}, {0x1d, 6},
46 {0x1e, 6}, {0x1f, 6}, {0x7fb, 11}, {0x18, 6}};
47
48 static const uint8_t tail_xtra[3] = {0, 2, 3};
49
grpc_chttp2_base64_encode(const grpc_slice & input)50 grpc_slice grpc_chttp2_base64_encode(const grpc_slice& input) {
51 size_t input_length = GRPC_SLICE_LENGTH(input);
52 size_t input_triplets = input_length / 3;
53 size_t tail_case = input_length % 3;
54 size_t output_length = (input_triplets * 4) + tail_xtra[tail_case];
55 grpc_slice output = GRPC_SLICE_MALLOC(output_length);
56 const uint8_t* in = GRPC_SLICE_START_PTR(input);
57 char* out = reinterpret_cast<char*> GRPC_SLICE_START_PTR(output);
58 size_t i;
59
60 // encode full triplets
61 for (i = 0; i < input_triplets; i++) {
62 out[0] = alphabet[in[0] >> 2];
63 out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
64 out[2] = alphabet[((in[1] & 0xf) << 2) | (in[2] >> 6)];
65 out[3] = alphabet[in[2] & 0x3f];
66 out += 4;
67 in += 3;
68 }
69
70 // encode the remaining bytes
71 switch (tail_case) {
72 case 0:
73 break;
74 case 1:
75 out[0] = alphabet[in[0] >> 2];
76 out[1] = alphabet[(in[0] & 0x3) << 4];
77 out += 2;
78 in += 1;
79 break;
80 case 2:
81 out[0] = alphabet[in[0] >> 2];
82 out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
83 out[2] = alphabet[(in[1] & 0xf) << 2];
84 out += 3;
85 in += 2;
86 break;
87 }
88
89 CHECK(out == (char*)GRPC_SLICE_END_PTR(output));
90 CHECK(in == GRPC_SLICE_END_PTR(input));
91 return output;
92 }
93
grpc_chttp2_huffman_compress(const grpc_slice & input)94 grpc_slice grpc_chttp2_huffman_compress(const grpc_slice& input) {
95 size_t nbits;
96 const uint8_t* in;
97 uint8_t* out;
98 grpc_slice output;
99 uint64_t temp = 0;
100 uint32_t temp_length = 0;
101
102 nbits = 0;
103 for (in = GRPC_SLICE_START_PTR(input); in != GRPC_SLICE_END_PTR(input);
104 ++in) {
105 nbits += grpc_chttp2_huffsyms[*in].length;
106 }
107
108 output = GRPC_SLICE_MALLOC(nbits / 8 + (nbits % 8 != 0));
109 out = GRPC_SLICE_START_PTR(output);
110 for (in = GRPC_SLICE_START_PTR(input); in != GRPC_SLICE_END_PTR(input);
111 ++in) {
112 int sym = *in;
113 temp <<= grpc_chttp2_huffsyms[sym].length;
114 temp |= grpc_chttp2_huffsyms[sym].bits;
115 temp_length += grpc_chttp2_huffsyms[sym].length;
116
117 while (temp_length > 8) {
118 temp_length -= 8;
119 *out++ = static_cast<uint8_t>(temp >> temp_length);
120 }
121 }
122
123 if (temp_length) {
124 // NB: the following integer arithmetic operation needs to be in its
125 // expanded form due to the "integral promotion" performed (see section
126 // 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
127 // is then required to avoid the compiler warning
128 *out++ =
129 static_cast<uint8_t>(static_cast<uint8_t>(temp << (8u - temp_length)) |
130 static_cast<uint8_t>(0xffu >> temp_length));
131 }
132
133 CHECK(out == GRPC_SLICE_END_PTR(output));
134
135 return output;
136 }
137
138 struct huff_out {
139 uint32_t temp;
140 uint32_t temp_length;
141 uint8_t* out;
142 };
enc_flush_some(huff_out * out)143 static void enc_flush_some(huff_out* out) {
144 while (out->temp_length > 8) {
145 out->temp_length -= 8;
146 *out->out++ = static_cast<uint8_t>(out->temp >> out->temp_length);
147 }
148 }
149
enc_add2(huff_out * out,uint8_t a,uint8_t b,uint32_t * wire_size)150 static void enc_add2(huff_out* out, uint8_t a, uint8_t b, uint32_t* wire_size) {
151 *wire_size += 2;
152 b64_huff_sym sa = huff_alphabet[a];
153 b64_huff_sym sb = huff_alphabet[b];
154 out->temp = (out->temp << (sa.length + sb.length)) |
155 (static_cast<uint32_t>(sa.bits) << sb.length) | sb.bits;
156 out->temp_length +=
157 static_cast<uint32_t>(sa.length) + static_cast<uint32_t>(sb.length);
158 enc_flush_some(out);
159 }
160
enc_add1(huff_out * out,uint8_t a,uint32_t * wire_size)161 static void enc_add1(huff_out* out, uint8_t a, uint32_t* wire_size) {
162 *wire_size += 1;
163 b64_huff_sym sa = huff_alphabet[a];
164 out->temp = (out->temp << sa.length) | sa.bits;
165 out->temp_length += sa.length;
166 enc_flush_some(out);
167 }
168
grpc_chttp2_base64_encode_and_huffman_compress(const grpc_slice & input,uint32_t * wire_size)169 grpc_slice grpc_chttp2_base64_encode_and_huffman_compress(
170 const grpc_slice& input, uint32_t* wire_size) {
171 size_t input_length = GRPC_SLICE_LENGTH(input);
172 size_t input_triplets = input_length / 3;
173 size_t tail_case = input_length % 3;
174 size_t output_syms = (input_triplets * 4) + tail_xtra[tail_case];
175 size_t max_output_bits = 11 * output_syms;
176 size_t max_output_length = (max_output_bits / 8) + (max_output_bits % 8 != 0);
177 grpc_slice output = GRPC_SLICE_MALLOC(max_output_length);
178 const uint8_t* in = GRPC_SLICE_START_PTR(input);
179 uint8_t* start_out = GRPC_SLICE_START_PTR(output);
180 huff_out out;
181 size_t i;
182
183 out.temp = 0;
184 out.temp_length = 0;
185 out.out = start_out;
186 *wire_size = 0;
187
188 // encode full triplets
189 for (i = 0; i < input_triplets; i++) {
190 const uint8_t low_to_high = static_cast<uint8_t>((in[0] & 0x3) << 4);
191 const uint8_t high_to_low = in[1] >> 4;
192 enc_add2(&out, in[0] >> 2, low_to_high | high_to_low, wire_size);
193
194 const uint8_t a = static_cast<uint8_t>((in[1] & 0xf) << 2);
195 const uint8_t b = (in[2] >> 6);
196 enc_add2(&out, a | b, in[2] & 0x3f, wire_size);
197 in += 3;
198 }
199
200 // encode the remaining bytes
201 switch (tail_case) {
202 case 0:
203 break;
204 case 1:
205 enc_add2(&out, in[0] >> 2, static_cast<uint8_t>((in[0] & 0x3) << 4),
206 wire_size);
207 in += 1;
208 break;
209 case 2: {
210 const uint8_t low_to_high = static_cast<uint8_t>((in[0] & 0x3) << 4);
211 const uint8_t high_to_low = in[1] >> 4;
212 enc_add2(&out, in[0] >> 2, low_to_high | high_to_low, wire_size);
213 enc_add1(&out, static_cast<uint8_t>((in[1] & 0xf) << 2), wire_size);
214 in += 2;
215 break;
216 }
217 }
218
219 if (out.temp_length) {
220 // NB: the following integer arithmetic operation needs to be in its
221 // expanded form due to the "integral promotion" performed (see section
222 // 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
223 // is then required to avoid the compiler warning
224 *out.out++ = static_cast<uint8_t>(
225 static_cast<uint8_t>(out.temp << (8u - out.temp_length)) |
226 static_cast<uint8_t>(0xffu >> out.temp_length));
227 }
228
229 CHECK(out.out <= GRPC_SLICE_END_PTR(output));
230 GRPC_SLICE_SET_LENGTH(output, out.out - start_out);
231
232 CHECK(in == GRPC_SLICE_END_PTR(input));
233 return output;
234 }
235