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