1/*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2013 Tatsuhiro Tsujikawa
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25#include "nghttp2_hd_huffman.h"
26
27#include <string.h>
28#include <assert.h>
29#include <stdio.h>
30
31#include "nghttp2_hd.h"
32#include "nghttp2_net.h"
33
34size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len) {
35  size_t i;
36  size_t nbits = 0;
37
38  for (i = 0; i < len; ++i) {
39    nbits += huff_sym_table[src[i]].nbits;
40  }
41  /* pad the prefix of EOS (256) */
42  return (nbits + 7) / 8;
43}
44
45int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src,
46                           size_t srclen) {
47  const nghttp2_huff_sym *sym;
48  const uint8_t *end = src + srclen;
49  uint64_t code = 0;
50  uint32_t x;
51  size_t nbits = 0;
52  size_t avail;
53  int rv;
54
55  avail = nghttp2_bufs_cur_avail(bufs);
56
57  for (; src != end;) {
58    sym = &huff_sym_table[*src++];
59    code |= (uint64_t)sym->code << (32 - nbits);
60    nbits += sym->nbits;
61    if (nbits < 32) {
62      continue;
63    }
64    if (avail >= 4) {
65      x = htonl((uint32_t)(code >> 32));
66      memcpy(bufs->cur->buf.last, &x, 4);
67      bufs->cur->buf.last += 4;
68      avail -= 4;
69      code <<= 32;
70      nbits -= 32;
71      continue;
72    }
73
74    for (; nbits >= 8;) {
75      rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56));
76      if (rv != 0) {
77        return rv;
78      }
79      code <<= 8;
80      nbits -= 8;
81    }
82
83    avail = nghttp2_bufs_cur_avail(bufs);
84  }
85
86  for (; nbits >= 8;) {
87    rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56));
88    if (rv != 0) {
89      return rv;
90    }
91    code <<= 8;
92    nbits -= 8;
93  }
94
95  if (nbits) {
96    rv = nghttp2_bufs_addb(
97        bufs, (uint8_t)((uint8_t)(code >> 56) | ((1 << (8 - nbits)) - 1)));
98    if (rv != 0) {
99      return rv;
100    }
101  }
102
103  return 0;
104}
105
106void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx) {
107  ctx->fstate = NGHTTP2_HUFF_ACCEPTED;
108}
109
110ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
111                               nghttp2_buf *buf, const uint8_t *src,
112                               size_t srclen, int final) {
113  const uint8_t *end = src + srclen;
114  nghttp2_huff_decode node = {ctx->fstate, 0};
115  const nghttp2_huff_decode *t = &node;
116  uint8_t c;
117
118  /* We use the decoding algorithm described in
119     http://graphics.ics.uci.edu/pub/Prefix.pdf */
120  for (; src != end;) {
121    c = *src++;
122    t = &huff_decode_table[t->fstate & 0x1ff][c >> 4];
123    if (t->fstate & NGHTTP2_HUFF_SYM) {
124      *buf->last++ = t->sym;
125    }
126
127    t = &huff_decode_table[t->fstate & 0x1ff][c & 0xf];
128    if (t->fstate & NGHTTP2_HUFF_SYM) {
129      *buf->last++ = t->sym;
130    }
131  }
132
133  ctx->fstate = t->fstate;
134
135  if (final && !(ctx->fstate & NGHTTP2_HUFF_ACCEPTED)) {
136    return NGHTTP2_ERR_HEADER_COMP;
137  }
138
139  return (ssize_t)srclen;
140}
141
142int nghttp2_hd_huff_decode_failure_state(nghttp2_hd_huff_decode_context *ctx) {
143  return ctx->fstate == 0x100;
144}
145