lsquic_crt_compress.c revision 2f4629f2 
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
165static int
166match_common_cert (lsquic_str_t * cert, lsquic_str_t * common_set_hashes,
167        uint64_t* out_hash, uint32_t* out_index);
168
169int
170lsquic_crt_init (void)
171{
172    unsigned i;
173
174    s_ccsbuf = lsquic_str_new(NULL, 0);
175    if (!s_ccsbuf)
176        return -1;
177    for (i=0 ;i<common_certs_num; ++i)
178    {
179        if (0 != lsquic_str_append(s_ccsbuf, (const char *)&common_cert_set[i].hash, 8))
180            return -1;
181    }
182    return 0;
183}
184
185
186lsquic_str_t *
187lsquic_get_common_certs_hash()
188{
189    return s_ccsbuf;
190}
191
192
193/* return 0 found, -1 not found */
194int
195lsquic_get_common_cert(uint64_t hash, uint32_t index, lsquic_str_t *buf)
196{
197    int i;
198    for (i = 0; i < common_certs_num; i++)
199    {
200        if (common_cert_set[i].hash == hash)
201        {
202            if (index < common_cert_set[i].num_certs)
203            {
204                lsquic_str_setto(buf, (const char *) common_cert_set[i].certs[index],
205                         common_cert_set[i].lens[index]);
206                return 0;
207            }
208            break;
209        }
210    }
211    return -1;
212}
213
214
215static int
216comp_ls_str (lsquic_str_t * a, const void * b, size_t b_len)
217{
218    size_t a_len;
219    int r;
220
221    a_len = lsquic_str_len(a);
222    r = memcmp(lsquic_str_buf(a), b, a_len < b_len ? a_len : b_len);
223    if (r)
224        return r;
225    else
226        return (a_len > b_len) - (b_len > a_len);
227}
228
229
230/* 0, matched -1, error */
231static int
232match_common_cert (lsquic_str_t * cert, lsquic_str_t * common_set_hashes,
233        uint64_t* out_hash, uint32_t* out_index)
234{
235    size_t i, j;
236    int n;
237    uint64_t hash;
238    size_t min, max, mid;
239
240    if (lsquic_str_len(common_set_hashes) % sizeof(uint64_t) != 0)
241        return -1;
242
243    for (i = 0; i < lsquic_str_len(common_set_hashes) / sizeof(uint64_t); i++)
244    {
245        memcpy(&hash, lsquic_str_buf(common_set_hashes) + i * sizeof(uint64_t),
246               sizeof(uint64_t));
247
248        for (j = 0; j < common_certs_num; j++)
249        {
250            if (common_cert_set[j].hash != hash)
251                continue;
252
253            if (common_cert_set[j].num_certs == 0)
254                continue;
255
256            min = 0;
257            max = common_cert_set[j].num_certs - 1;
258            while (max >= min)
259            {
260                mid = min + ((max - min) / 2);
261                n = comp_ls_str(cert, common_cert_set[j].certs[mid],
262                                 common_cert_set[j].lens[mid]);
263                if (n < 0)
264                {
265                    if (mid == 0)
266                        break;
267                    max = mid - 1;
268                }
269                else if (n > 0)
270                    min = mid + 1;
271                else
272                {
273                    *out_hash = hash;
274                    *out_index = mid;
275                    return 0;
276                }
277            }
278        }
279    }
280
281    return -1;
282}
283
284
285/* result is written to dict */
286static void
287make_zlib_dict_for_entries(cert_entry_t *entries,
288                                lsquic_str_t **certs, size_t certs_count,
289                                lsquic_str_t *dict)
290{
291    int i;
292    size_t zlib_dict_size = 0;
293    for (i = certs_count - 1; i >= 0; --i)
294    {
295        if (entries[i].type != ENTRY_COMPRESSED)
296        {
297            zlib_dict_size += lsquic_str_len(certs[i]);
298        }
299    }
300
301    // At the end of the dictionary is a block of common certificate substrings.
302    zlib_dict_size += sizeof(common_cert_sub_strings);
303
304    for (i = certs_count - 1; i >= 0; --i)
305    {
306        if (entries[i].type != ENTRY_COMPRESSED)
307        {
308            lsquic_str_append(dict, lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
309        }
310    }
311
312    lsquic_str_append(dict, (const char *)common_cert_sub_strings, sizeof(common_cert_sub_strings));
313    assert((size_t)lsquic_str_len(dict) == zlib_dict_size);
314}
315
316
317static
318void get_certs_hash(lsquic_str_t *certs, size_t certs_count, uint64_t *hashs)
319{
320    size_t i;
321    for(i = 0; i < certs_count; ++i)
322    {
323        hashs[i] = lsquic_fnv1a_64((const uint8_t *)lsquic_str_buf(&certs[i]), lsquic_str_len(&certs[i]));
324    }
325}
326
327
328static void get_certs_entries(lsquic_str_t **certs, size_t certs_count,
329                              lsquic_str_t *client_common_set_hashes,
330                              lsquic_str_t *client_cached_cert_hashes,
331                              cert_entry_t *entries)
332{
333    size_t i;
334    int j;
335    cert_entry_t *entry;
336    uint64_t hash, cached_hash;
337    bool cached;
338
339    const bool cached_valid = (lsquic_str_len(client_cached_cert_hashes) % sizeof(uint64_t) == 0)
340                                && (lsquic_str_len(client_cached_cert_hashes) > 0);
341
342    assert(&entries[certs_count - 1]);
343
344    for (i = 0; i<certs_count; ++i)
345    {
346        entry = &entries[i];
347        if (cached_valid)
348        {
349            cached = false;
350            hash = lsquic_fnv1a_64((const uint8_t *)lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
351
352            for (j = 0; j < (int)lsquic_str_len(client_cached_cert_hashes);
353                 j += sizeof(uint64_t))
354            {
355                memcpy(&cached_hash, lsquic_str_buf(client_cached_cert_hashes) + j,
356                       sizeof(uint64_t));
357                if (hash != cached_hash)
358                    continue;
359
360                entry->type = ENTRY_CACHED;
361                entry->hash = hash;
362                cached = true;
363                break;
364            }
365
366            if (cached)
367                continue;
368        }
369
370        if (0 == match_common_cert(certs[i], client_common_set_hashes,
371            &entry->set_hash, &entry->index))
372        {
373            entry->type = ENTRY_COMMON;
374            continue;
375        }
376
377        entry->type = ENTRY_COMPRESSED;
378   }
379}
380
381static size_t
382get_entries_size(cert_entry_t *entries, size_t entries_count)
383{
384    size_t i;
385    size_t entries_size = 0;
386    for(i=0; i<entries_count; ++i)
387    {
388        entries_size++;
389        switch (entries[i].type)
390        {
391        case ENTRY_COMPRESSED:
392            break;
393        case ENTRY_CACHED:
394            entries_size += sizeof(uint64_t);
395            break;
396        case ENTRY_COMMON:
397            entries_size += sizeof(uint64_t) + sizeof(uint32_t);
398            break;
399        default:
400            break;
401        }
402    }
403    entries_size++;  /* for end marker */
404    return entries_size;
405}
406
407static
408void serialize_cert_entries(uint8_t* out, int *out_len, cert_entry_t *entries,
409                            size_t entries_count)
410{
411    size_t i;
412    uint8_t *start = out;
413    for(i=0; i<entries_count; ++i)
414    {
415        *out++ = (uint8_t)(entries[i].type);
416        switch (entries[i].type)
417        {
418        case ENTRY_COMPRESSED:
419            break;
420        case ENTRY_CACHED:
421            memcpy(out, &entries[i].hash, sizeof(uint64_t));
422            out += sizeof(uint64_t);
423            break;
424        case ENTRY_COMMON:
425            memcpy(out, &entries[i].set_hash, sizeof(uint64_t));
426            out += sizeof(uint64_t);
427            memcpy(out, &entries[i].index, sizeof(uint32_t));
428            out += sizeof(uint32_t);
429            break;
430        default:
431            break;
432        }
433    }
434
435    *out++ = 0;  // end marker
436    *out_len = out - start;
437}
438
439
440int
441lsquic_get_certs_count(lsquic_str_t *compressed_crt_buf)
442{
443    char *in = lsquic_str_buf(compressed_crt_buf);
444    char *in_end = in + lsquic_str_len(compressed_crt_buf);
445    size_t idx = 0;
446    uint8_t type_byte;
447
448    for (;;)
449    {
450        if (in >= in_end)
451            return -1;
452
453        type_byte = in[0];
454        ++in;
455        if (type_byte == 0)
456            break;
457
458        ++idx;
459        switch(type_byte)
460        {
461        case ENTRY_COMPRESSED:
462            break;
463        case ENTRY_CACHED:
464        {
465            if (in_end - in < (int)sizeof(uint64_t))
466                return -1;
467            in += sizeof(uint64_t);
468            break;
469        }
470        case ENTRY_COMMON:
471        {
472            if (in_end - in < (int)(sizeof(uint64_t) + sizeof(uint32_t)))
473                return -1;
474            in += sizeof(uint64_t) + sizeof(uint32_t);
475            break;
476        }
477        default:
478            return -1;
479        }
480    }
481    return idx;
482}
483
484
485/* return 0: OK, -1, error */
486static int parse_entries(const unsigned char **in_out, const unsigned char *const in_end,
487                         lsquic_str_t *cached_certs, size_t cached_certs_count,
488                         cert_entry_t *out_entries,
489                         lsquic_str_t **out_certs, size_t *out_certs_count)
490{
491    const unsigned char *in = *in_out;
492    size_t idx = 0;
493    uint64_t* cached_hashes;
494    cert_entry_t *entry;
495    lsquic_str_t *cert;
496    uint8_t type_byte;
497    int rv;
498    size_t i;
499
500    cached_hashes = NULL;
501
502    for (;;)
503    {
504        /* XXX potential invalid read */
505        type_byte = in[0];
506        ++in;
507
508        if (type_byte == 0)
509            break;
510
511        entry = &out_entries[idx];
512        cert = out_certs[idx];
513        /* XXX This seems dangerous -- there is no guard that `idx' does not
514         * exceed `out_certs_count'.
515         */
516        lsquic_str_d(cert);
517
518        ++idx;
519        entry->type = type_byte;
520        switch (entry->type)
521        {
522        case ENTRY_COMPRESSED:
523            break;
524        case ENTRY_CACHED:
525        {
526            memcpy(&entry->hash, in, sizeof(uint64_t));
527            in += sizeof(uint64_t);
528
529            if (!cached_hashes)
530            {
531                cached_hashes = malloc(cached_certs_count * sizeof(uint64_t));;
532                if (!cached_hashes)
533                    goto err;
534                get_certs_hash(cached_certs, cached_certs_count, cached_hashes);
535            }
536
537            for (i=0; i<cached_certs_count; ++i)
538            {
539                if (cached_hashes[i] == entry->hash)
540                {
541                    lsquic_str_append(cert, lsquic_str_buf(&cached_certs[i]),
542                                  lsquic_str_len(&cached_certs[i]));
543                    break;
544                }
545            }
546            /* XXX: return -1 if not found?  Logic removed in
547                                4fd7e76bc031ac637e76c7f0930aff53f5b71705 */
548            break;
549        }
550        case ENTRY_COMMON:
551        {
552            memcpy(&entry->set_hash, in, sizeof(uint64_t));
553            in += sizeof(uint64_t);
554            memcpy(&entry->index, in, sizeof(uint32_t));
555            in += sizeof(uint32_t);
556
557            if (0 == lsquic_get_common_cert(entry->set_hash, entry->index, cert))
558                break;
559            else
560                goto err;
561        }
562        default:
563            goto err;
564        }
565    }
566
567    rv = 0;
568    *in_out = in;
569    *out_certs_count = idx;
570
571  cleanup:
572    free(cached_hashes);
573    return rv;
574
575  err:
576    rv = -1;
577    goto cleanup;
578}
579
580
581/* return 0 for OK */
582int
583lsquic_compress_certs (lsquic_str_t **certs, size_t certs_count,
584                   lsquic_str_t *client_common_set_hashes,
585                   lsquic_str_t *client_cached_cert_hashes,
586                   lsquic_str_t *result)
587{
588    int rv;
589    size_t i;
590    size_t uncompressed_size = 0, compressed_size = 0 ;
591    z_stream z;
592    lsquic_str_t *dict;
593    size_t entries_size, result_length;
594    int out_len;
595    uint8_t* out;
596    uint32_t tmp_size_32;
597    cert_entry_t *entries;
598
599    entries = malloc(sizeof(cert_entry_t) * certs_count);
600    if (!entries)
601        return -1;
602
603    dict = lsquic_str_new(NULL, 0);
604    if (!dict)
605        goto err;
606
607    get_certs_entries(certs, certs_count, client_common_set_hashes,
608                              client_cached_cert_hashes, entries);
609
610    for (i = 0; i < certs_count; i++)
611    {
612        if (entries[i].type == ENTRY_COMPRESSED)
613        {
614             /*uint32_t length + cert content*/
615            uncompressed_size += 4 + lsquic_str_len(certs[i]);
616        }
617    }
618
619    if (uncompressed_size > 0)
620    {
621        memset(&z, 0, sizeof(z));
622        if (Z_OK != deflateInit(&z, Z_DEFAULT_COMPRESSION))
623            goto err;
624
625        make_zlib_dict_for_entries(entries, certs, certs_count, dict);
626        if(Z_OK != deflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
627            goto err;
628        compressed_size = deflateBound(&z, uncompressed_size);
629    }
630
631    entries_size = get_entries_size(entries, certs_count);
632    result_length = entries_size + (uncompressed_size > 0 ? 4 : 0) +
633                    compressed_size;
634    lsquic_str_prealloc(result, result_length);
635
636    out = (unsigned char *)lsquic_str_buf(result);
637    serialize_cert_entries(out, &out_len, entries, certs_count);
638    out += entries_size;
639
640    if (uncompressed_size == 0)
641    {
642        lsquic_str_setlen(result, entries_size);
643        rv = 0;
644        goto cleanup;
645    }
646
647    tmp_size_32 = uncompressed_size;
648    memcpy(out, &tmp_size_32, sizeof(uint32_t));
649    out += sizeof(uint32_t);
650
651    z.next_out = out;
652    z.avail_out = compressed_size;
653
654    for (i = 0; i < certs_count; ++i)
655    {
656        if (entries[i].type != ENTRY_COMPRESSED)
657            continue;
658
659        tmp_size_32 = lsquic_str_len(certs[i]);
660        z.next_in = (uint8_t*)(&tmp_size_32);
661        z.avail_in = sizeof(tmp_size_32);
662        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
663            goto err;
664        z.next_in = (unsigned char *)lsquic_str_buf(certs[i]);
665        z.avail_in = lsquic_str_len(certs[i]);
666        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
667            goto err;
668    }
669
670    z.avail_in = 0;
671    if (Z_STREAM_END != deflate(&z, Z_FINISH))
672        goto err;
673
674    rv = 0;
675    result_length -= z.avail_out;
676    lsquic_str_setlen(result, result_length);
677
678  cleanup:
679    free(entries);
680    if (dict)
681        lsquic_str_delete(dict);
682    if (uncompressed_size)
683        deflateEnd(&z);
684    return rv;
685
686  err:
687    rv = -1;
688    goto cleanup;
689}
690
691
692/* 0: ok */
693int
694lsquic_decompress_certs (const unsigned char *in, const unsigned char *in_end,
695                     lsquic_str_t *cached_certs, size_t cached_certs_count,
696                     lsquic_str_t **out_certs, size_t *out_certs_count)
697{
698    int ret;
699    size_t i;
700    uint8_t* uncompressed_data, *uncompressed_data_buf;
701    lsquic_str_t *dict;
702    uint32_t uncompressed_size;
703    size_t count = *out_certs_count;
704    cert_entry_t *entries;
705    z_stream z;
706
707    assert(*out_certs_count > 0 && *out_certs_count < 10000
708            && "Call lsquic_get_certs_count() to get right certificates count first and make enough room for out_certs_count");
709
710    if (count == 0 || count > 10000)
711        return -1;
712
713    dict = lsquic_str_new(NULL, 0);
714    if (!dict)
715        return -1;
716
717    uncompressed_data_buf = NULL;
718#ifdef WIN32
719    uncompressed_data = NULL;
720#endif
721    entries = malloc(count * sizeof(cert_entry_t));
722    if (!entries)
723        goto err;
724
725    ret = parse_entries(&in, in_end, cached_certs, cached_certs_count,
726                  entries, out_certs, out_certs_count);
727    if (ret)
728        goto err;
729
730    /* re-assign count with real valus */
731    count = *out_certs_count;
732
733    if (in < in_end)
734    {
735        if (in_end - in < (int)sizeof(uint32_t))
736            goto err;
737
738        memcpy(&uncompressed_size, in, sizeof(uncompressed_size));
739        in += sizeof(uint32_t);
740        /* XXX Is 128 KB an arbitrary limit or is there a reason behind it? */
741        if (uncompressed_size > 128 * 1024)
742            goto err;
743
744        uncompressed_data_buf = uncompressed_data = malloc(uncompressed_size);
745        if (!uncompressed_data)
746            goto err;
747
748        memset(&z, 0, sizeof(z));
749        z.next_out  = uncompressed_data;
750        z.avail_out = uncompressed_size;
751        z.next_in   = (unsigned char *) in;
752        z.avail_in  = in_end - in;
753
754        if (Z_OK != inflateInit(&z))
755            goto err;
756
757        ret = inflate(&z, Z_FINISH);
758        if (ret == Z_NEED_DICT)
759        {
760            lsquic_str_d(dict);
761            make_zlib_dict_for_entries(entries, out_certs, count, dict);
762            if (Z_OK != inflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
763                goto err;
764            ret = inflate(&z, Z_FINISH);
765        }
766
767        if (Z_STREAM_END != ret || z.avail_out > 0 || z.avail_in > 0)
768            goto err;
769    }
770    else
771        uncompressed_size = 0;
772
773    for (i = 0; i < count; i++)
774    {
775        switch (entries[i].type)
776        {
777          case ENTRY_COMPRESSED:
778              if (uncompressed_size < sizeof(uint32_t))
779                  goto err;
780              lsquic_str_d(out_certs[i]);
781              uint32_t cert_len;
782              memcpy(&cert_len, uncompressed_data, sizeof(cert_len));
783              uncompressed_data += sizeof(uint32_t);
784              uncompressed_size -= sizeof(uint32_t);
785              if (uncompressed_size < cert_len)
786                  goto err;
787              lsquic_str_append(out_certs[i], (const char *)uncompressed_data, cert_len);
788              uncompressed_data += cert_len;
789              uncompressed_size -= cert_len;
790              break;
791          case ENTRY_CACHED:
792          case ENTRY_COMMON:
793          default:
794            break;
795        }
796    }
797
798  cleanup:
799    lsquic_str_delete(dict);
800    free(entries);
801    if (uncompressed_data_buf)
802        inflateEnd(&z);
803    free(uncompressed_data_buf);
804    if (0 == uncompressed_size)
805        return 0;
806    else
807        return -1;
808
809  err:
810    uncompressed_size = 1;  /* This triggers return -1 above */
811    goto cleanup;
812}
813
814
815void
816lsquic_crt_cleanup (void)
817{
818    if (s_ccsbuf)
819    {
820        lsquic_str_delete(s_ccsbuf);
821        s_ccsbuf = NULL;
822    }
823}
824