lsquic_crt_compress.c revision 7d09751d 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdbool.h>
4#include <string.h>
5#include <time.h>
6#include <zlib.h>
7
8#include <openssl/ssl.h>
9#ifndef WIN32
10#else
11#include <stdlib.h>
12#include <vc_compat.h>
13#endif
14
15#include "lsquic_int_types.h"
16#include "lsquic_crypto.h"
17#include "lsquic_crt_compress.h"
18#include "lsquic_util.h"
19
20#include "lsquic_str.h"
21
22#include "common_cert_set_2.c"
23#include "common_cert_set_3.c"
24
25/*
26 * common_cert_sub_strings contains ~1500 bytes of common certificate substrings
27 * as a dictionary of zlib from the Alexa Top 5000 set.
28 */
29static const unsigned char common_cert_sub_strings[] = {
30    0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x25, 0x04,
31    0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03,
32    0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03, 0x02, 0x30,
33    0x5f, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x86, 0xf8, 0x42, 0x04, 0x01,
34    0x06, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86, 0xfd, 0x6d, 0x01, 0x07,
35    0x17, 0x01, 0x30, 0x33, 0x20, 0x45, 0x78, 0x74, 0x65, 0x6e, 0x64, 0x65,
36    0x64, 0x20, 0x56, 0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x69, 0x6f, 0x6e,
37    0x20, 0x53, 0x20, 0x4c, 0x69, 0x6d, 0x69, 0x74, 0x65, 0x64, 0x31, 0x34,
38    0x20, 0x53, 0x53, 0x4c, 0x20, 0x43, 0x41, 0x30, 0x1e, 0x17, 0x0d, 0x31,
39    0x32, 0x20, 0x53, 0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x53, 0x65, 0x72,
40    0x76, 0x65, 0x72, 0x20, 0x43, 0x41, 0x30, 0x2d, 0x61, 0x69, 0x61, 0x2e,
41    0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
42    0x2f, 0x45, 0x2d, 0x63, 0x72, 0x6c, 0x2e, 0x76, 0x65, 0x72, 0x69, 0x73,
43    0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x45, 0x2e, 0x63, 0x65,
44    0x72, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01,
45    0x01, 0x05, 0x05, 0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x4a, 0x2e, 0x63,
46    0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x73, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x73,
47    0x2f, 0x63, 0x70, 0x73, 0x20, 0x28, 0x63, 0x29, 0x30, 0x30, 0x09, 0x06,
48    0x03, 0x55, 0x1d, 0x13, 0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x30, 0x0d,
49    0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05,
50    0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x7b, 0x30, 0x1d, 0x06, 0x03, 0x55,
51    0x1d, 0x0e, 0x30, 0x82, 0x01, 0x22, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86,
52    0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x01, 0x05, 0x00, 0x03, 0x82, 0x01,
53    0x0f, 0x00, 0x30, 0x82, 0x01, 0x0a, 0x02, 0x82, 0x01, 0x01, 0x00, 0xd2,
54    0x6f, 0x64, 0x6f, 0x63, 0x61, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x43, 0x2e,
55    0x63, 0x72, 0x6c, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x0e, 0x04, 0x16,
56    0x04, 0x14, 0xb4, 0x2e, 0x67, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x73, 0x69,
57    0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x30, 0x0b, 0x06, 0x03,
58    0x55, 0x1d, 0x0f, 0x04, 0x04, 0x03, 0x02, 0x01, 0x30, 0x0d, 0x06, 0x09,
59    0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05, 0x00, 0x30,
60    0x81, 0xca, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03, 0x55, 0x04, 0x06, 0x13,
61    0x02, 0x55, 0x53, 0x31, 0x10, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x04, 0x08,
62    0x13, 0x07, 0x41, 0x72, 0x69, 0x7a, 0x6f, 0x6e, 0x61, 0x31, 0x13, 0x30,
63    0x11, 0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x0a, 0x53, 0x63, 0x6f, 0x74,
64    0x74, 0x73, 0x64, 0x61, 0x6c, 0x65, 0x31, 0x1a, 0x30, 0x18, 0x06, 0x03,
65    0x55, 0x04, 0x0a, 0x13, 0x11, 0x47, 0x6f, 0x44, 0x61, 0x64, 0x64, 0x79,
66    0x2e, 0x63, 0x6f, 0x6d, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31, 0x33,
67    0x30, 0x31, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x2a, 0x68, 0x74, 0x74,
68    0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66, 0x69, 0x63,
69    0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79,
70    0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74,
71    0x6f, 0x72, 0x79, 0x31, 0x30, 0x30, 0x2e, 0x06, 0x03, 0x55, 0x04, 0x03,
72    0x13, 0x27, 0x47, 0x6f, 0x20, 0x44, 0x61, 0x64, 0x64, 0x79, 0x20, 0x53,
73    0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x43, 0x65, 0x72, 0x74, 0x69, 0x66,
74    0x69, 0x63, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x20, 0x41, 0x75, 0x74, 0x68,
75    0x6f, 0x72, 0x69, 0x74, 0x79, 0x31, 0x11, 0x30, 0x0f, 0x06, 0x03, 0x55,
76    0x04, 0x05, 0x13, 0x08, 0x30, 0x37, 0x39, 0x36, 0x39, 0x32, 0x38, 0x37,
77    0x30, 0x1e, 0x17, 0x0d, 0x31, 0x31, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d,
78    0x0f, 0x01, 0x01, 0xff, 0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x0c,
79    0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff, 0x04, 0x02, 0x30, 0x00,
80    0x30, 0x1d, 0x30, 0x0f, 0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff,
81    0x04, 0x05, 0x30, 0x03, 0x01, 0x01, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55,
82    0x1d, 0x25, 0x04, 0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05,
83    0x05, 0x07, 0x03, 0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07,
84    0x03, 0x02, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d, 0x0f, 0x01, 0x01, 0xff,
85    0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x33, 0x06, 0x03, 0x55, 0x1d,
86    0x1f, 0x04, 0x2c, 0x30, 0x2a, 0x30, 0x28, 0xa0, 0x26, 0xa0, 0x24, 0x86,
87    0x22, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x72, 0x6c, 0x2e,
88    0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
89    0x67, 0x64, 0x73, 0x31, 0x2d, 0x32, 0x30, 0x2a, 0x30, 0x28, 0x06, 0x08,
90    0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x02, 0x01, 0x16, 0x1c, 0x68, 0x74,
91    0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76, 0x65,
92    0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x63,
93    0x70, 0x73, 0x30, 0x34, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x5a, 0x17,
94    0x0d, 0x31, 0x33, 0x30, 0x35, 0x30, 0x39, 0x06, 0x08, 0x2b, 0x06, 0x01,
95    0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x2d, 0x68, 0x74, 0x74, 0x70, 0x3a,
96    0x2f, 0x2f, 0x73, 0x30, 0x39, 0x30, 0x37, 0x06, 0x08, 0x2b, 0x06, 0x01,
97    0x05, 0x05, 0x07, 0x02, 0x30, 0x44, 0x06, 0x03, 0x55, 0x1d, 0x20, 0x04,
98    0x3d, 0x30, 0x3b, 0x30, 0x39, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86,
99    0xf8, 0x45, 0x01, 0x07, 0x17, 0x06, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03,
100    0x55, 0x04, 0x06, 0x13, 0x02, 0x47, 0x42, 0x31, 0x1b, 0x53, 0x31, 0x17,
101    0x30, 0x15, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x13, 0x0e, 0x56, 0x65, 0x72,
102    0x69, 0x53, 0x69, 0x67, 0x6e, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31,
103    0x1f, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x16, 0x56, 0x65,
104    0x72, 0x69, 0x53, 0x69, 0x67, 0x6e, 0x20, 0x54, 0x72, 0x75, 0x73, 0x74,
105    0x20, 0x4e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x31, 0x3b, 0x30, 0x39,
106    0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x32, 0x54, 0x65, 0x72, 0x6d, 0x73,
107    0x20, 0x6f, 0x66, 0x20, 0x75, 0x73, 0x65, 0x20, 0x61, 0x74, 0x20, 0x68,
108    0x74, 0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76,
109    0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
110    0x72, 0x70, 0x61, 0x20, 0x28, 0x63, 0x29, 0x30, 0x31, 0x10, 0x30, 0x0e,
111    0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x07, 0x53, 0x31, 0x13, 0x30, 0x11,
112    0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x0a, 0x47, 0x31, 0x13, 0x30, 0x11,
113    0x06, 0x0b, 0x2b, 0x06, 0x01, 0x04, 0x01, 0x82, 0x37, 0x3c, 0x02, 0x01,
114    0x03, 0x13, 0x02, 0x55, 0x31, 0x16, 0x30, 0x14, 0x06, 0x03, 0x55, 0x04,
115    0x03, 0x14, 0x31, 0x19, 0x30, 0x17, 0x06, 0x03, 0x55, 0x04, 0x03, 0x13,
116    0x31, 0x1d, 0x30, 0x1b, 0x06, 0x03, 0x55, 0x04, 0x0f, 0x13, 0x14, 0x50,
117    0x72, 0x69, 0x76, 0x61, 0x74, 0x65, 0x20, 0x4f, 0x72, 0x67, 0x61, 0x6e,
118    0x69, 0x7a, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x31, 0x12, 0x31, 0x21, 0x30,
119    0x1f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x18, 0x44, 0x6f, 0x6d, 0x61,
120    0x69, 0x6e, 0x20, 0x43, 0x6f, 0x6e, 0x74, 0x72, 0x6f, 0x6c, 0x20, 0x56,
121    0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x65, 0x64, 0x31, 0x14, 0x31, 0x31,
122    0x30, 0x2f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x28, 0x53, 0x65, 0x65,
123    0x20, 0x77, 0x77, 0x77, 0x2e, 0x72, 0x3a, 0x2f, 0x2f, 0x73, 0x65, 0x63,
124    0x75, 0x72, 0x65, 0x2e, 0x67, 0x47, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x53,
125    0x69, 0x67, 0x6e, 0x31, 0x53, 0x65, 0x72, 0x76, 0x65, 0x72, 0x43, 0x41,
126    0x2e, 0x63, 0x72, 0x6c, 0x56, 0x65, 0x72, 0x69, 0x53, 0x69, 0x67, 0x6e,
127    0x20, 0x43, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x33, 0x20, 0x45, 0x63, 0x72,
128    0x6c, 0x2e, 0x67, 0x65, 0x6f, 0x74, 0x72, 0x75, 0x73, 0x74, 0x2e, 0x63,
129    0x6f, 0x6d, 0x2f, 0x63, 0x72, 0x6c, 0x73, 0x2f, 0x73, 0x64, 0x31, 0x1a,
130    0x30, 0x18, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x68, 0x74, 0x74, 0x70, 0x3a,
131    0x2f, 0x2f, 0x45, 0x56, 0x49, 0x6e, 0x74, 0x6c, 0x2d, 0x63, 0x63, 0x72,
132    0x74, 0x2e, 0x67, 0x77, 0x77, 0x77, 0x2e, 0x67, 0x69, 0x63, 0x65, 0x72,
133    0x74, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x31, 0x6f, 0x63, 0x73, 0x70, 0x2e,
134    0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
135    0x30, 0x39, 0x72, 0x61, 0x70, 0x69, 0x64, 0x73, 0x73, 0x6c, 0x2e, 0x63,
136    0x6f, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63,
137    0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74, 0x6f, 0x72,
138    0x79, 0x2f, 0x30, 0x81, 0x80, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05,
139    0x07, 0x01, 0x01, 0x04, 0x74, 0x30, 0x72, 0x30, 0x24, 0x06, 0x08, 0x2b,
140    0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x01, 0x86, 0x18, 0x68, 0x74, 0x74,
141    0x70, 0x3a, 0x2f, 0x2f, 0x6f, 0x63, 0x73, 0x70, 0x2e, 0x67, 0x6f, 0x64,
142    0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x30, 0x4a, 0x06,
143    0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x3e, 0x68,
144    0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66,
145    0x69, 0x63, 0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64,
146    0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73,
147    0x69, 0x74, 0x6f, 0x72, 0x79, 0x2f, 0x67, 0x64, 0x5f, 0x69, 0x6e, 0x74,
148    0x65, 0x72, 0x6d, 0x65, 0x64, 0x69, 0x61, 0x74, 0x65, 0x2e, 0x63, 0x72,
149    0x74, 0x30, 0x1f, 0x06, 0x03, 0x55, 0x1d, 0x23, 0x04, 0x18, 0x30, 0x16,
150    0x80, 0x14, 0xfd, 0xac, 0x61, 0x32, 0x93, 0x6c, 0x45, 0xd6, 0xe2, 0xee,
151    0x85, 0x5f, 0x9a, 0xba, 0xe7, 0x76, 0x99, 0x68, 0xcc, 0xe7, 0x30, 0x27,
152    0x86, 0x29, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x86, 0x30,
153    0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x73,
154};
155
156#define common_certs_num 2
157const common_cert_t common_cert_set[common_certs_num] = {
158    {common_certs2_num, common_certs2, common_certs2_lens, common_certs2_hash},
159    {common_certs3_num, common_certs3, common_certs3_lens, common_certs3_hash},
160};
161
162
163static lsquic_str_t *s_ccsbuf;
164
165lsquic_str_t * get_common_certs_hash()
166{
167    int i;
168    if (s_ccsbuf == NULL)
169    {
170        s_ccsbuf = lsquic_str_new(NULL, 0);
171        for (i=0 ;i<common_certs_num; ++i)
172        {
173            lsquic_str_append(s_ccsbuf, (const char *)&common_cert_set[i].hash, 8);
174        }
175    }
176    return s_ccsbuf;
177}
178
179
180/* return 0 found, -1 not found */
181int get_common_cert(uint64_t hash, uint32_t index, lsquic_str_t *buf)
182{
183    int i;
184    for (i = 0; i < common_certs_num; i++)
185    {
186        if (common_cert_set[i].hash == hash)
187        {
188            if (index < common_cert_set[i].num_certs)
189            {
190                lsquic_str_setto(buf, (const char *) common_cert_set[i].certs[index],
191                         common_cert_set[i].lens[index]);
192                return 0;
193            }
194            break;
195        }
196    }
197    return -1;
198}
199
200
201static int
202comp_ls_str (lsquic_str_t * a, const void * b, size_t b_len)
203{
204    size_t a_len;
205    int r;
206
207    a_len = lsquic_str_len(a);
208    r = memcmp(lsquic_str_buf(a), b, a_len < b_len ? a_len : b_len);
209    if (r)
210        return r;
211    else
212        return (a_len > b_len) - (b_len > a_len);
213}
214
215
216/* 0, matched -1, error */
217int match_common_cert(lsquic_str_t * cert, lsquic_str_t * common_set_hashes,
218        uint64_t* out_hash, uint32_t* out_index)
219{
220    size_t i, j;
221    int n;
222    uint64_t hash;
223    size_t min, max, mid;
224
225    if (lsquic_str_len(common_set_hashes) % sizeof(uint64_t) != 0)
226        return -1;
227
228    for (i = 0; i < lsquic_str_len(common_set_hashes) / sizeof(uint64_t); i++)
229    {
230        memcpy(&hash, lsquic_str_buf(common_set_hashes) + i * sizeof(uint64_t),
231               sizeof(uint64_t));
232
233        for (j = 0; j < common_certs_num; j++)
234        {
235            if (common_cert_set[j].hash != hash)
236                continue;
237
238            if (common_cert_set[j].num_certs == 0)
239                continue;
240
241            min = 0;
242            max = common_cert_set[j].num_certs - 1;
243            while (max >= min)
244            {
245                mid = min + ((max - min) / 2);
246                n = comp_ls_str(cert, common_cert_set[j].certs[mid],
247                                 common_cert_set[j].lens[mid]);
248                if (n < 0)
249                {
250                    if (mid == 0)
251                        break;
252                    max = mid - 1;
253                }
254                else if (n > 0)
255                    min = mid + 1;
256                else
257                {
258                    *out_hash = hash;
259                    *out_index = mid;
260                    return 0;
261                }
262            }
263        }
264    }
265
266    return -1;
267}
268
269
270/* result is written to dict */
271static void
272make_zlib_dict_for_entries(cert_entry_t *entries,
273                                lsquic_str_t **certs, size_t certs_count,
274                                lsquic_str_t *dict)
275{
276    int i;
277    size_t zlib_dict_size = 0;
278    for (i = certs_count - 1; i >= 0; --i)
279    {
280        if (entries[i].type != ENTRY_COMPRESSED)
281        {
282            zlib_dict_size += lsquic_str_len(certs[i]);
283        }
284    }
285
286    // At the end of the dictionary is a block of common certificate substrings.
287    zlib_dict_size += sizeof(common_cert_sub_strings);
288
289    for (i = certs_count - 1; i >= 0; --i)
290    {
291        if (entries[i].type != ENTRY_COMPRESSED)
292        {
293            lsquic_str_append(dict, lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
294        }
295    }
296
297    lsquic_str_append(dict, (const char *)common_cert_sub_strings, sizeof(common_cert_sub_strings));
298    assert((size_t)lsquic_str_len(dict) == zlib_dict_size);
299}
300
301
302void get_certs_hash(lsquic_str_t *certs, size_t certs_count, uint64_t *hashs)
303{
304    size_t i;
305    for(i = 0; i < certs_count; ++i)
306    {
307        hashs[i] = fnv1a_64((const uint8_t *)lsquic_str_buf(&certs[i]), lsquic_str_len(&certs[i]));
308    }
309}
310
311
312static void get_certs_entries(lsquic_str_t **certs, size_t certs_count,
313                              lsquic_str_t *client_common_set_hashes,
314                              lsquic_str_t *client_cached_cert_hashes,
315                              cert_entry_t *entries)
316{
317    size_t i;
318    int j;
319    cert_entry_t *entry;
320    uint64_t hash, cached_hash;
321    bool cached;
322
323    const bool cached_valid = (lsquic_str_len(client_cached_cert_hashes) % sizeof(uint64_t) == 0)
324                                && (lsquic_str_len(client_cached_cert_hashes) > 0);
325
326    assert(&entries[certs_count - 1]);
327
328    for (i = 0; i<certs_count; ++i)
329    {
330        entry = &entries[i];
331        if (cached_valid)
332        {
333            cached = false;
334            hash = fnv1a_64((const uint8_t *)lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
335
336            for (j = 0; j < (int)lsquic_str_len(client_cached_cert_hashes);
337                 j += sizeof(uint64_t))
338            {
339                memcpy(&cached_hash, lsquic_str_buf(client_cached_cert_hashes) + j,
340                       sizeof(uint64_t));
341                if (hash != cached_hash)
342                    continue;
343
344                entry->type = ENTRY_CACHED;
345                entry->hash = hash;
346                cached = true;
347                break;
348            }
349
350            if (cached)
351                continue;
352        }
353
354        if (0 == match_common_cert(certs[i], client_common_set_hashes,
355            &entry->set_hash, &entry->index))
356        {
357            entry->type = ENTRY_COMMON;
358            continue;
359        }
360
361        entry->type = ENTRY_COMPRESSED;
362   }
363}
364
365size_t get_entries_size(cert_entry_t *entries, size_t entries_count)
366{
367    size_t i;
368    size_t entries_size = 0;
369    for(i=0; i<entries_count; ++i)
370    {
371        entries_size++;
372        switch (entries[i].type)
373        {
374        case ENTRY_COMPRESSED:
375            break;
376        case ENTRY_CACHED:
377            entries_size += sizeof(uint64_t);
378            break;
379        case ENTRY_COMMON:
380            entries_size += sizeof(uint64_t) + sizeof(uint32_t);
381            break;
382        default:
383            break;
384        }
385    }
386    entries_size++;  /* for end marker */
387    return entries_size;
388}
389
390void serialize_cert_entries(uint8_t* out, int *out_len, cert_entry_t *entries,
391                            size_t entries_count)
392{
393    size_t i;
394    uint8_t *start = out;
395    for(i=0; i<entries_count; ++i)
396    {
397        *out++ = (uint8_t)(entries[i].type);
398        switch (entries[i].type)
399        {
400        case ENTRY_COMPRESSED:
401            break;
402        case ENTRY_CACHED:
403            memcpy(out, &entries[i].hash, sizeof(uint64_t));
404            out += sizeof(uint64_t);
405            break;
406        case ENTRY_COMMON:
407            memcpy(out, &entries[i].set_hash, sizeof(uint64_t));
408            out += sizeof(uint64_t);
409            memcpy(out, &entries[i].index, sizeof(uint32_t));
410            out += sizeof(uint32_t);
411            break;
412        default:
413            break;
414        }
415    }
416
417    *out++ = 0;  // end marker
418    *out_len = out - start;
419}
420
421
422int get_certs_count(lsquic_str_t *compressed_crt_buf)
423{
424    char *in = lsquic_str_buf(compressed_crt_buf);
425    char *in_end = in + lsquic_str_len(compressed_crt_buf);
426    size_t idx = 0;
427    uint8_t type_byte;
428
429    for (;;)
430    {
431        if (in >= in_end)
432            return -1;
433
434        type_byte = in[0];
435        ++in;
436        if (type_byte == 0)
437            break;
438
439        ++idx;
440        switch(type_byte)
441        {
442        case ENTRY_COMPRESSED:
443            break;
444        case ENTRY_CACHED:
445        {
446            if (in_end - in < (int)sizeof(uint64_t))
447                return -1;
448            in += sizeof(uint64_t);
449            break;
450        }
451        case ENTRY_COMMON:
452        {
453            if (in_end - in < (int)(sizeof(uint64_t) + sizeof(uint32_t)))
454                return -1;
455            in += sizeof(uint64_t) + sizeof(uint32_t);
456            break;
457        }
458        default:
459            return -1;
460        }
461    }
462    return idx;
463}
464
465
466/* return 0: OK, -1, error */
467static int parse_entries(const unsigned char **in_out, const unsigned char *const in_end,
468                         lsquic_str_t *cached_certs, size_t cached_certs_count,
469                         cert_entry_t *out_entries,
470                         lsquic_str_t **out_certs, size_t *out_certs_count)
471{
472    const unsigned char *in = *in_out;
473    size_t idx = 0;
474    uint64_t* cached_hashes;
475    cert_entry_t *entry;
476    lsquic_str_t *cert;
477    uint8_t type_byte;
478    int rv;
479    size_t i;
480
481    cached_hashes = NULL;
482
483    for (;;)
484    {
485        /* XXX potential invalid read */
486        type_byte = in[0];
487        ++in;
488
489        if (type_byte == 0)
490            break;
491
492        entry = &out_entries[idx];
493        cert = out_certs[idx];
494        /* XXX This seems dangerous -- there is no guard that `idx' does not
495         * exceed `out_certs_count'.
496         */
497        lsquic_str_d(cert);
498
499        ++idx;
500        entry->type = type_byte;
501        switch (entry->type)
502        {
503        case ENTRY_COMPRESSED:
504            break;
505        case ENTRY_CACHED:
506        {
507            memcpy(&entry->hash, in, sizeof(uint64_t));
508            in += sizeof(uint64_t);
509
510            if (!cached_hashes)
511            {
512                cached_hashes = malloc(cached_certs_count * sizeof(uint64_t));;
513                if (!cached_hashes)
514                    goto err;
515                get_certs_hash(cached_certs, cached_certs_count, cached_hashes);
516            }
517
518            for (i=0; i<cached_certs_count; ++i)
519            {
520                if (cached_hashes[i] == entry->hash)
521                {
522                    lsquic_str_append(cert, lsquic_str_buf(&cached_certs[i]),
523                                  lsquic_str_len(&cached_certs[i]));
524                    break;
525                }
526            }
527            /* XXX: return -1 if not found?  Logic removed in
528                                4fd7e76bc031ac637e76c7f0930aff53f5b71705 */
529            break;
530        }
531        case ENTRY_COMMON:
532        {
533            memcpy(&entry->set_hash, in, sizeof(uint64_t));
534            in += sizeof(uint64_t);
535            memcpy(&entry->index, in, sizeof(uint32_t));
536            in += sizeof(uint32_t);
537
538            if (0 == get_common_cert(entry->set_hash, entry->index, cert))
539                break;
540            else
541                goto err;
542        }
543        default:
544            goto err;
545        }
546    }
547
548    rv = 0;
549    *in_out = in;
550    *out_certs_count = idx;
551
552  cleanup:
553    free(cached_hashes);
554    return rv;
555
556  err:
557    rv = -1;
558    goto cleanup;
559}
560
561
562/* return 0 for OK */
563int compress_certs(lsquic_str_t **certs, size_t certs_count,
564                   lsquic_str_t *client_common_set_hashes,
565                   lsquic_str_t *client_cached_cert_hashes,
566                   lsquic_str_t *result)
567{
568    int rv;
569    size_t i;
570    size_t uncompressed_size = 0, compressed_size = 0 ;
571    z_stream z;
572    lsquic_str_t *dict;
573    size_t entries_size, result_length;
574    int out_len;
575    uint8_t* out;
576    uint32_t tmp_size_32;
577    cert_entry_t *entries;
578
579    entries = malloc(sizeof(cert_entry_t) * certs_count);
580    if (!entries)
581        return -1;
582
583    dict = lsquic_str_new(NULL, 0);
584    if (!dict)
585        goto err;
586
587    get_certs_entries(certs, certs_count, client_common_set_hashes,
588                              client_cached_cert_hashes, entries);
589
590    for (i = 0; i < certs_count; i++)
591    {
592        if (entries[i].type == ENTRY_COMPRESSED)
593        {
594             /*uint32_t length + cert content*/
595            uncompressed_size += 4 + lsquic_str_len(certs[i]);
596        }
597    }
598
599    if (uncompressed_size > 0)
600    {
601        memset(&z, 0, sizeof(z));
602        if (Z_OK != deflateInit(&z, Z_DEFAULT_COMPRESSION))
603            goto err;
604
605        make_zlib_dict_for_entries(entries, certs, certs_count, dict);
606        if(Z_OK != deflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
607            goto err;
608        compressed_size = deflateBound(&z, uncompressed_size);
609    }
610
611    entries_size = get_entries_size(entries, certs_count);
612    result_length = entries_size + (uncompressed_size > 0 ? 4 : 0) +
613                    compressed_size;
614    lsquic_str_prealloc(result, result_length);
615
616    out = (unsigned char *)lsquic_str_buf(result);
617    serialize_cert_entries(out, &out_len, entries, certs_count);
618    out += entries_size;
619
620    if (uncompressed_size == 0)
621    {
622        lsquic_str_setlen(result, entries_size);
623        rv = 0;
624        goto cleanup;
625    }
626
627    tmp_size_32 = uncompressed_size;
628    memcpy(out, &tmp_size_32, sizeof(uint32_t));
629    out += sizeof(uint32_t);
630
631    z.next_out = out;
632    z.avail_out = compressed_size;
633
634    for (i = 0; i < certs_count; ++i)
635    {
636        if (entries[i].type != ENTRY_COMPRESSED)
637            continue;
638
639        tmp_size_32 = lsquic_str_len(certs[i]);
640        z.next_in = (uint8_t*)(&tmp_size_32);
641        z.avail_in = sizeof(tmp_size_32);
642        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
643            goto err;
644        z.next_in = (unsigned char *)lsquic_str_buf(certs[i]);
645        z.avail_in = lsquic_str_len(certs[i]);
646        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
647            goto err;
648    }
649
650    z.avail_in = 0;
651    if (Z_STREAM_END != deflate(&z, Z_FINISH))
652        goto err;
653
654    rv = 0;
655    result_length -= z.avail_out;
656    lsquic_str_setlen(result, result_length);
657
658  cleanup:
659    free(entries);
660    if (dict)
661        lsquic_str_delete(dict);
662    if (uncompressed_size)
663        deflateEnd(&z);
664    return rv;
665
666  err:
667    rv = -1;
668    goto cleanup;
669}
670
671
672/* 0: ok */
673int decompress_certs(const unsigned char *in, const unsigned char *in_end,
674                     lsquic_str_t *cached_certs, size_t cached_certs_count,
675                     lsquic_str_t **out_certs, size_t *out_certs_count)
676{
677    int ret;
678    size_t i;
679    uint8_t* uncompressed_data, *uncompressed_data_buf;
680    lsquic_str_t *dict;
681    uint32_t uncompressed_size;
682    size_t count = *out_certs_count;
683    cert_entry_t *entries;
684    z_stream z;
685
686    assert(*out_certs_count > 0 && *out_certs_count < 10000
687            && "Call get_certs_count() to get right certificates count first and make enough room for out_certs_count");
688
689    if (count == 0 || count > 10000)
690        return -1;
691
692    dict = lsquic_str_new(NULL, 0);
693    if (!dict)
694        return -1;
695
696    uncompressed_data_buf = NULL;
697#ifdef WIN32
698    uncompressed_data = NULL;
699#endif
700    entries = malloc(count * sizeof(cert_entry_t));
701    if (!entries)
702        goto err;
703
704    ret = parse_entries(&in, in_end, cached_certs, cached_certs_count,
705                  entries, out_certs, out_certs_count);
706    if (ret)
707        goto err;
708
709    /* re-assign count with real valus */
710    count = *out_certs_count;
711
712    if (in < in_end)
713    {
714        if (in_end - in < (int)sizeof(uint32_t))
715            goto err;
716
717        memcpy(&uncompressed_size, in, sizeof(uncompressed_size));
718        in += sizeof(uint32_t);
719        /* XXX Is 128 KB an arbitrary limit or is there a reason behind it? */
720        if (uncompressed_size > 128 * 1024)
721            goto err;
722
723        uncompressed_data_buf = uncompressed_data = malloc(uncompressed_size);
724        if (!uncompressed_data)
725            goto err;
726
727        memset(&z, 0, sizeof(z));
728        z.next_out  = uncompressed_data;
729        z.avail_out = uncompressed_size;
730        z.next_in   = (unsigned char *) in;
731        z.avail_in  = in_end - in;
732
733        if (Z_OK != inflateInit(&z))
734            goto err;
735
736        ret = inflate(&z, Z_FINISH);
737        if (ret == Z_NEED_DICT)
738        {
739            lsquic_str_d(dict);
740            make_zlib_dict_for_entries(entries, out_certs, count, dict);
741            if (Z_OK != inflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
742                goto err;
743            ret = inflate(&z, Z_FINISH);
744        }
745
746        if (Z_STREAM_END != ret || z.avail_out > 0 || z.avail_in > 0)
747            goto err;
748    }
749    else
750        uncompressed_size = 0;
751
752    for (i = 0; i < count; i++)
753    {
754        switch (entries[i].type)
755        {
756          case ENTRY_COMPRESSED:
757              if (uncompressed_size < sizeof(uint32_t))
758                  goto err;
759              lsquic_str_d(out_certs[i]);
760              uint32_t cert_len;
761              memcpy(&cert_len, uncompressed_data, sizeof(cert_len));
762              uncompressed_data += sizeof(uint32_t);
763              uncompressed_size -= sizeof(uint32_t);
764              if (uncompressed_size < cert_len)
765                  goto err;
766              lsquic_str_append(out_certs[i], (const char *)uncompressed_data, cert_len);
767              uncompressed_data += cert_len;
768              uncompressed_size -= cert_len;
769              break;
770          case ENTRY_CACHED:
771          case ENTRY_COMMON:
772          default:
773            break;
774        }
775    }
776
777  cleanup:
778    lsquic_str_delete(dict);
779    free(entries);
780    if (uncompressed_data_buf)
781        inflateEnd(&z);
782    free(uncompressed_data_buf);
783    if (0 == uncompressed_size)
784        return 0;
785    else
786        return -1;
787
788  err:
789    uncompressed_size = 1;  /* This triggers return -1 above */
790    goto cleanup;
791}
792
793
794void
795lsquic_crt_cleanup (void)
796{
797    if (s_ccsbuf)
798    {
799        lsquic_str_delete(s_ccsbuf);
800        s_ccsbuf = NULL;
801    }
802}
803