legacy-libs/grpc-cloned/deps/grpc/src/core/ext/transport/chttp2/transport/bin_encoder.cc

   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 <grpc/support/port_platform.h>
  20
  21 #include "src/core/ext/transport/chttp2/transport/bin_encoder.h"
  22
  23 #include <string.h>
  24
  25 #include <grpc/support/log.h>
  26 #include "src/core/ext/transport/chttp2/transport/huffsyms.h"
  27
  28 static const char alphabet[] =
  29     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  30
  31 typedef struct {
  32   uint16_t bits;
  33   uint8_t length;
  34 } b64_huff_sym;
  35
  36 static const b64_huff_sym huff_alphabet[64] = {
  37     {0x21, 6}, {0x5d, 7}, {0x5e, 7},   {0x5f, 7}, {0x60, 7}, {0x61, 7},
  38     {0x62, 7}, {0x63, 7}, {0x64, 7},   {0x65, 7}, {0x66, 7}, {0x67, 7},
  39     {0x68, 7}, {0x69, 7}, {0x6a, 7},   {0x6b, 7}, {0x6c, 7}, {0x6d, 7},
  40     {0x6e, 7}, {0x6f, 7}, {0x70, 7},   {0x71, 7}, {0x72, 7}, {0xfc, 8},
  41     {0x73, 7}, {0xfd, 8}, {0x3, 5},    {0x23, 6}, {0x4, 5},  {0x24, 6},
  42     {0x5, 5},  {0x25, 6}, {0x26, 6},   {0x27, 6}, {0x6, 5},  {0x74, 7},
  43     {0x75, 7}, {0x28, 6}, {0x29, 6},   {0x2a, 6}, {0x7, 5},  {0x2b, 6},
  44     {0x76, 7}, {0x2c, 6}, {0x8, 5},    {0x9, 5},  {0x2d, 6}, {0x77, 7},
  45     {0x78, 7}, {0x79, 7}, {0x7a, 7},   {0x7b, 7}, {0x0, 5},  {0x1, 5},
  46     {0x2, 5},  {0x19, 6}, {0x1a, 6},   {0x1b, 6}, {0x1c, 6}, {0x1d, 6},
  47     {0x1e, 6}, {0x1f, 6}, {0x7fb, 11}, {0x18, 6}};
  48
  49 static const uint8_t tail_xtra[3] = {0, 2, 3};
  50
  51 grpc_slice grpc_chttp2_base64_encode(const grpc_slice& input) {
  52   size_t input_length = GRPC_SLICE_LENGTH(input);
  53   size_t input_triplets = input_length / 3;
  54   size_t tail_case = input_length % 3;
  55   size_t output_length = input_triplets * 4 + tail_xtra[tail_case];
  56   grpc_slice output = GRPC_SLICE_MALLOC(output_length);
  57   const uint8_t* in = GRPC_SLICE_START_PTR(input);
  58   char* out = reinterpret_cast<char*> GRPC_SLICE_START_PTR(output);
  59   size_t i;
  60
  61   /* encode full triplets */
  62   for (i = 0; i < input_triplets; i++) {
  63     out[0] = alphabet[in[0] >> 2];
  64     out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
  65     out[2] = alphabet[((in[1] & 0xf) << 2) | (in[2] >> 6)];
  66     out[3] = alphabet[in[2] & 0x3f];
  67     out += 4;
  68     in += 3;
  69   }
  70
  71   /* encode the remaining bytes */
  72   switch (tail_case) {
  73     case 0:
  74       break;
  75     case 1:
  76       out[0] = alphabet[in[0] >> 2];
  77       out[1] = alphabet[(in[0] & 0x3) << 4];
  78       out += 2;
  79       in += 1;
  80       break;
  81     case 2:
  82       out[0] = alphabet[in[0] >> 2];
  83       out[1] = alphabet[((in[0] & 0x3) << 4) | (in[1] >> 4)];
  84       out[2] = alphabet[(in[1] & 0xf) << 2];
  85       out += 3;
  86       in += 2;
  87       break;
  88   }
  89
  90   GPR_ASSERT(out == (char*)GRPC_SLICE_END_PTR(output));
  91   GPR_ASSERT(in == GRPC_SLICE_END_PTR(input));
  92   return output;
  93 }
  94
  95 grpc_slice grpc_chttp2_huffman_compress(const grpc_slice& input) {
  96   size_t nbits;
  97   const uint8_t* in;
  98   uint8_t* out;
  99   grpc_slice output;
 100   uint32_t temp = 0;
 101   uint32_t temp_length = 0;
 102
 103   nbits = 0;
 104   for (in = GRPC_SLICE_START_PTR(input); in != GRPC_SLICE_END_PTR(input);
 105        ++in) {
 106     nbits += grpc_chttp2_huffsyms[*in].length;
 107   }
 108
 109   output = GRPC_SLICE_MALLOC(nbits / 8 + (nbits % 8 != 0));
 110   out = GRPC_SLICE_START_PTR(output);
 111   for (in = GRPC_SLICE_START_PTR(input); in != GRPC_SLICE_END_PTR(input);
 112        ++in) {
 113     int sym = *in;
 114     temp <<= grpc_chttp2_huffsyms[sym].length;
 115     temp |= grpc_chttp2_huffsyms[sym].bits;
 116     temp_length += grpc_chttp2_huffsyms[sym].length;
 117
 118     while (temp_length > 8) {
 119       temp_length -= 8;
 120       *out++ = static_cast<uint8_t>(temp >> temp_length);
 121     }
 122   }
 123
 124   if (temp_length) {
 125     /* NB: the following integer arithmetic operation needs to be in its
 126      * expanded form due to the "integral promotion" performed (see section
 127      * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
 128      * is then required to avoid the compiler warning */
 129     *out++ =
 130         static_cast<uint8_t>(static_cast<uint8_t>(temp << (8u - temp_length)) |
 131                              static_cast<uint8_t>(0xffu >> temp_length));
 132   }
 133
 134   GPR_ASSERT(out == GRPC_SLICE_END_PTR(output));
 135
 136   return output;
 137 }
 138
 139 typedef struct {
 140   uint32_t temp;
 141   uint32_t temp_length;
 142   uint8_t* out;
 143 } huff_out;
 144
 145 static void enc_flush_some(huff_out* out) {
 146   while (out->temp_length > 8) {
 147     out->temp_length -= 8;
 148     *out->out++ = static_cast<uint8_t>(out->temp >> out->temp_length);
 149   }
 150 }
 151
 152 static void enc_add2(huff_out* out, uint8_t a, uint8_t b) {
 153   b64_huff_sym sa = huff_alphabet[a];
 154   b64_huff_sym sb = huff_alphabet[b];
 155   out->temp = (out->temp << (sa.length + sb.length)) |
 156               (static_cast<uint32_t>(sa.bits) << sb.length) | sb.bits;
 157   out->temp_length +=
 158       static_cast<uint32_t>(sa.length) + static_cast<uint32_t>(sb.length);
 159   enc_flush_some(out);
 160 }
 161
 162 static void enc_add1(huff_out* out, uint8_t a) {
 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
 169 grpc_slice grpc_chttp2_base64_encode_and_huffman_compress(
 170     const grpc_slice& input) {
 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
 187   /* encode full triplets */
 188   for (i = 0; i < input_triplets; i++) {
 189     const uint8_t low_to_high = static_cast<uint8_t>((in[0] & 0x3) << 4);
 190     const uint8_t high_to_low = in[1] >> 4;
 191     enc_add2(&out, in[0] >> 2, low_to_high | high_to_low);
 192
 193     const uint8_t a = static_cast<uint8_t>((in[1] & 0xf) << 2);
 194     const uint8_t b = (in[2] >> 6);
 195     enc_add2(&out, a | b, in[2] & 0x3f);
 196     in += 3;
 197   }
 198
 199   /* encode the remaining bytes */
 200   switch (tail_case) {
 201     case 0:
 202       break;
 203     case 1:
 204       enc_add2(&out, in[0] >> 2, static_cast<uint8_t>((in[0] & 0x3) << 4));
 205       in += 1;
 206       break;
 207     case 2: {
 208       const uint8_t low_to_high = static_cast<uint8_t>((in[0] & 0x3) << 4);
 209       const uint8_t high_to_low = in[1] >> 4;
 210       enc_add2(&out, in[0] >> 2, low_to_high | high_to_low);
 211       enc_add1(&out, static_cast<uint8_t>((in[1] & 0xf) << 2));
 212       in += 2;
 213       break;
 214     }
 215   }
 216
 217   if (out.temp_length) {
 218     /* NB: the following integer arithmetic operation needs to be in its
 219      * expanded form due to the "integral promotion" performed (see section
 220      * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
 221      * is then required to avoid the compiler warning */
 222     *out.out++ = static_cast<uint8_t>(
 223         static_cast<uint8_t>(out.temp << (8u - out.temp_length)) |
 224         static_cast<uint8_t>(0xffu >> out.temp_length));
 225   }
 226
 227   GPR_ASSERT(out.out <= GRPC_SLICE_END_PTR(output));
 228   GRPC_SLICE_SET_LENGTH(output, out.out - start_out);
 229
 230   GPR_ASSERT(in == GRPC_SLICE_END_PTR(input));
 231   return output;
 232 }