Coverage Report

Created: 2025-06-24 07:01

/src/ghostpdl/brotli/c/common/transform.c
Line
Count
Source (jump to first uncovered line)
1
/* Copyright 2013 Google Inc. All Rights Reserved.
2
3
   Distributed under MIT license.
4
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5
*/
6
7
#include "transform.h"
8
9
#if defined(__cplusplus) || defined(c_plusplus)
10
extern "C" {
11
#endif
12
13
/* RFC 7932 transforms string data */
14
static const char kPrefixSuffix[217] =
15
      "\1 \2, \10 of the \4 of \2s \1.\5 and \4 "
16
/* 0x  _0 _2  __5        _E    _3  _6 _8     _E */
17
      "in \1\"\4 to \2\">\1\n\2. \1]\5 for \3 a \6 "
18
/* 2x     _3_ _5    _A_  _D_ _F  _2 _4     _A   _E */
19
      "that \1\'\6 with \6 from \4 by \1(\6. T"
20
/* 4x       _5_ _7      _E      _5    _A _C */
21
      "he \4 on \4 as \4 is \4ing \2\n\t\1:\3ed "
22
/* 6x     _3    _8    _D    _2    _7_ _ _A _C */
23
      "\2=\"\4 at \3ly \1,\2=\'\5.com/\7. This \5"
24
/* 8x  _0 _ _3    _8   _C _E _ _1     _7       _F */
25
      " not \3er \3al \4ful \4ive \5less \4es"
26
/* Ax       _5   _9   _D    _2    _7     _D */
27
      "t \4ize \2\xc2\xa0\4ous \5 the \2e "; /* \0 - implicit trailing zero. */
28
/* Cx    _2    _7___ ___ _A    _F     _5        _8 */
29
30
static const uint16_t kPrefixSuffixMap[50] = {
31
  0x00, 0x02, 0x05, 0x0E, 0x13, 0x16, 0x18, 0x1E, 0x23, 0x25,
32
  0x2A, 0x2D, 0x2F, 0x32, 0x34, 0x3A, 0x3E, 0x45, 0x47, 0x4E,
33
  0x55, 0x5A, 0x5C, 0x63, 0x68, 0x6D, 0x72, 0x77, 0x7A, 0x7C,
34
  0x80, 0x83, 0x88, 0x8C, 0x8E, 0x91, 0x97, 0x9F, 0xA5, 0xA9,
35
  0xAD, 0xB2, 0xB7, 0xBD, 0xC2, 0xC7, 0xCA, 0xCF, 0xD5, 0xD8
36
};
37
38
/* RFC 7932 transforms */
39
static const uint8_t kTransformsData[] = {
40
  49, BROTLI_TRANSFORM_IDENTITY, 49,
41
  49, BROTLI_TRANSFORM_IDENTITY, 0,
42
   0, BROTLI_TRANSFORM_IDENTITY, 0,
43
  49, BROTLI_TRANSFORM_OMIT_FIRST_1, 49,
44
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 0,
45
  49, BROTLI_TRANSFORM_IDENTITY, 47,
46
   0, BROTLI_TRANSFORM_IDENTITY, 49,
47
   4, BROTLI_TRANSFORM_IDENTITY, 0,
48
  49, BROTLI_TRANSFORM_IDENTITY, 3,
49
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 49,
50
  49, BROTLI_TRANSFORM_IDENTITY, 6,
51
  49, BROTLI_TRANSFORM_OMIT_FIRST_2, 49,
52
  49, BROTLI_TRANSFORM_OMIT_LAST_1, 49,
53
   1, BROTLI_TRANSFORM_IDENTITY, 0,
54
  49, BROTLI_TRANSFORM_IDENTITY, 1,
55
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 0,
56
  49, BROTLI_TRANSFORM_IDENTITY, 7,
57
  49, BROTLI_TRANSFORM_IDENTITY, 9,
58
  48, BROTLI_TRANSFORM_IDENTITY, 0,
59
  49, BROTLI_TRANSFORM_IDENTITY, 8,
60
  49, BROTLI_TRANSFORM_IDENTITY, 5,
61
  49, BROTLI_TRANSFORM_IDENTITY, 10,
62
  49, BROTLI_TRANSFORM_IDENTITY, 11,
63
  49, BROTLI_TRANSFORM_OMIT_LAST_3, 49,
64
  49, BROTLI_TRANSFORM_IDENTITY, 13,
65
  49, BROTLI_TRANSFORM_IDENTITY, 14,
66
  49, BROTLI_TRANSFORM_OMIT_FIRST_3, 49,
67
  49, BROTLI_TRANSFORM_OMIT_LAST_2, 49,
68
  49, BROTLI_TRANSFORM_IDENTITY, 15,
69
  49, BROTLI_TRANSFORM_IDENTITY, 16,
70
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 49,
71
  49, BROTLI_TRANSFORM_IDENTITY, 12,
72
   5, BROTLI_TRANSFORM_IDENTITY, 49,
73
   0, BROTLI_TRANSFORM_IDENTITY, 1,
74
  49, BROTLI_TRANSFORM_OMIT_FIRST_4, 49,
75
  49, BROTLI_TRANSFORM_IDENTITY, 18,
76
  49, BROTLI_TRANSFORM_IDENTITY, 17,
77
  49, BROTLI_TRANSFORM_IDENTITY, 19,
78
  49, BROTLI_TRANSFORM_IDENTITY, 20,
79
  49, BROTLI_TRANSFORM_OMIT_FIRST_5, 49,
80
  49, BROTLI_TRANSFORM_OMIT_FIRST_6, 49,
81
  47, BROTLI_TRANSFORM_IDENTITY, 49,
82
  49, BROTLI_TRANSFORM_OMIT_LAST_4, 49,
83
  49, BROTLI_TRANSFORM_IDENTITY, 22,
84
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 49,
85
  49, BROTLI_TRANSFORM_IDENTITY, 23,
86
  49, BROTLI_TRANSFORM_IDENTITY, 24,
87
  49, BROTLI_TRANSFORM_IDENTITY, 25,
88
  49, BROTLI_TRANSFORM_OMIT_LAST_7, 49,
89
  49, BROTLI_TRANSFORM_OMIT_LAST_1, 26,
90
  49, BROTLI_TRANSFORM_IDENTITY, 27,
91
  49, BROTLI_TRANSFORM_IDENTITY, 28,
92
   0, BROTLI_TRANSFORM_IDENTITY, 12,
93
  49, BROTLI_TRANSFORM_IDENTITY, 29,
94
  49, BROTLI_TRANSFORM_OMIT_FIRST_9, 49,
95
  49, BROTLI_TRANSFORM_OMIT_FIRST_7, 49,
96
  49, BROTLI_TRANSFORM_OMIT_LAST_6, 49,
97
  49, BROTLI_TRANSFORM_IDENTITY, 21,
98
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 1,
99
  49, BROTLI_TRANSFORM_OMIT_LAST_8, 49,
100
  49, BROTLI_TRANSFORM_IDENTITY, 31,
101
  49, BROTLI_TRANSFORM_IDENTITY, 32,
102
  47, BROTLI_TRANSFORM_IDENTITY, 3,
103
  49, BROTLI_TRANSFORM_OMIT_LAST_5, 49,
104
  49, BROTLI_TRANSFORM_OMIT_LAST_9, 49,
105
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 1,
106
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 8,
107
   5, BROTLI_TRANSFORM_IDENTITY, 21,
108
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 0,
109
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 10,
110
  49, BROTLI_TRANSFORM_IDENTITY, 30,
111
   0, BROTLI_TRANSFORM_IDENTITY, 5,
112
  35, BROTLI_TRANSFORM_IDENTITY, 49,
113
  47, BROTLI_TRANSFORM_IDENTITY, 2,
114
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 17,
115
  49, BROTLI_TRANSFORM_IDENTITY, 36,
116
  49, BROTLI_TRANSFORM_IDENTITY, 33,
117
   5, BROTLI_TRANSFORM_IDENTITY, 0,
118
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 21,
119
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 5,
120
  49, BROTLI_TRANSFORM_IDENTITY, 37,
121
   0, BROTLI_TRANSFORM_IDENTITY, 30,
122
  49, BROTLI_TRANSFORM_IDENTITY, 38,
123
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 0,
124
  49, BROTLI_TRANSFORM_IDENTITY, 39,
125
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 49,
126
  49, BROTLI_TRANSFORM_IDENTITY, 34,
127
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 8,
128
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 12,
129
   0, BROTLI_TRANSFORM_IDENTITY, 21,
130
  49, BROTLI_TRANSFORM_IDENTITY, 40,
131
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 12,
132
  49, BROTLI_TRANSFORM_IDENTITY, 41,
133
  49, BROTLI_TRANSFORM_IDENTITY, 42,
134
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 17,
135
  49, BROTLI_TRANSFORM_IDENTITY, 43,
136
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 5,
137
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 10,
138
   0, BROTLI_TRANSFORM_IDENTITY, 34,
139
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 33,
140
  49, BROTLI_TRANSFORM_IDENTITY, 44,
141
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 5,
142
  45, BROTLI_TRANSFORM_IDENTITY, 49,
143
   0, BROTLI_TRANSFORM_IDENTITY, 33,
144
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 30,
145
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 30,
146
  49, BROTLI_TRANSFORM_IDENTITY, 46,
147
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 1,
148
  49, BROTLI_TRANSFORM_UPPERCASE_FIRST, 34,
149
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 33,
150
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 30,
151
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 1,
152
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 33,
153
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 21,
154
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 12,
155
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 5,
156
  49, BROTLI_TRANSFORM_UPPERCASE_ALL, 34,
157
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 12,
158
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 30,
159
   0, BROTLI_TRANSFORM_UPPERCASE_ALL, 34,
160
   0, BROTLI_TRANSFORM_UPPERCASE_FIRST, 34,
161
};
162
163
static const BrotliTransforms kBrotliTransforms = {
164
  sizeof(kPrefixSuffix),
165
  (const uint8_t*)kPrefixSuffix,
166
  kPrefixSuffixMap,
167
  sizeof(kTransformsData) / (3 * sizeof(kTransformsData[0])),
168
  kTransformsData,
169
  NULL,  /* no extra parameters */
170
  {0, 12, 27, 23, 42, 63, 56, 48, 59, 64}
171
};
172
173
0
const BrotliTransforms* BrotliGetTransforms(void) {
174
0
  return &kBrotliTransforms;
175
0
}
176
177
0
static int ToUpperCase(uint8_t* p) {
178
0
  if (p[0] < 0xC0) {
179
0
    if (p[0] >= 'a' && p[0] <= 'z') {
180
0
      p[0] ^= 32;
181
0
    }
182
0
    return 1;
183
0
  }
184
  /* An overly simplified uppercasing model for UTF-8. */
185
0
  if (p[0] < 0xE0) {
186
0
    p[1] ^= 32;
187
0
    return 2;
188
0
  }
189
  /* An arbitrary transform for three byte characters. */
190
0
  p[2] ^= 5;
191
0
  return 3;
192
0
}
193
194
0
static int Shift(uint8_t* word, int word_len, uint16_t parameter) {
195
  /* Limited sign extension: scalar < (1 << 24). */
196
0
  uint32_t scalar =
197
0
      (parameter & 0x7FFFu) + (0x1000000u - (parameter & 0x8000u));
198
0
  if (word[0] < 0x80) {
199
    /* 1-byte rune / 0sssssss / 7 bit scalar (ASCII). */
200
0
    scalar += (uint32_t)word[0];
201
0
    word[0] = (uint8_t)(scalar & 0x7Fu);
202
0
    return 1;
203
0
  } else if (word[0] < 0xC0) {
204
    /* Continuation / 10AAAAAA. */
205
0
    return 1;
206
0
  } else if (word[0] < 0xE0) {
207
    /* 2-byte rune / 110sssss AAssssss / 11 bit scalar. */
208
0
    if (word_len < 2) return 1;
209
0
    scalar += (uint32_t)((word[1] & 0x3Fu) | ((word[0] & 0x1Fu) << 6u));
210
0
    word[0] = (uint8_t)(0xC0 | ((scalar >> 6u) & 0x1F));
211
0
    word[1] = (uint8_t)((word[1] & 0xC0) | (scalar & 0x3F));
212
0
    return 2;
213
0
  } else if (word[0] < 0xF0) {
214
    /* 3-byte rune / 1110ssss AAssssss BBssssss / 16 bit scalar. */
215
0
    if (word_len < 3) return word_len;
216
0
    scalar += (uint32_t)((word[2] & 0x3Fu) | ((word[1] & 0x3Fu) << 6u) |
217
0
        ((word[0] & 0x0Fu) << 12u));
218
0
    word[0] = (uint8_t)(0xE0 | ((scalar >> 12u) & 0x0F));
219
0
    word[1] = (uint8_t)((word[1] & 0xC0) | ((scalar >> 6u) & 0x3F));
220
0
    word[2] = (uint8_t)((word[2] & 0xC0) | (scalar & 0x3F));
221
0
    return 3;
222
0
  } else if (word[0] < 0xF8) {
223
    /* 4-byte rune / 11110sss AAssssss BBssssss CCssssss / 21 bit scalar. */
224
0
    if (word_len < 4) return word_len;
225
0
    scalar += (uint32_t)((word[3] & 0x3Fu) | ((word[2] & 0x3Fu) << 6u) |
226
0
        ((word[1] & 0x3Fu) << 12u) | ((word[0] & 0x07u) << 18u));
227
0
    word[0] = (uint8_t)(0xF0 | ((scalar >> 18u) & 0x07));
228
0
    word[1] = (uint8_t)((word[1] & 0xC0) | ((scalar >> 12u) & 0x3F));
229
0
    word[2] = (uint8_t)((word[2] & 0xC0) | ((scalar >> 6u) & 0x3F));
230
0
    word[3] = (uint8_t)((word[3] & 0xC0) | (scalar & 0x3F));
231
0
    return 4;
232
0
  }
233
0
  return 1;
234
0
}
235
236
int BrotliTransformDictionaryWord(uint8_t* dst, const uint8_t* word, int len,
237
0
    const BrotliTransforms* transforms, int transform_idx) {
238
0
  int idx = 0;
239
0
  const uint8_t* prefix = BROTLI_TRANSFORM_PREFIX(transforms, transform_idx);
240
0
  uint8_t type = BROTLI_TRANSFORM_TYPE(transforms, transform_idx);
241
0
  const uint8_t* suffix = BROTLI_TRANSFORM_SUFFIX(transforms, transform_idx);
242
0
  {
243
0
    int prefix_len = *prefix++;
244
0
    while (prefix_len--) { dst[idx++] = *prefix++; }
245
0
  }
246
0
  {
247
0
    const int t = type;
248
0
    int i = 0;
249
0
    if (t <= BROTLI_TRANSFORM_OMIT_LAST_9) {
250
0
      len -= t;
251
0
    } else if (t >= BROTLI_TRANSFORM_OMIT_FIRST_1
252
0
        && t <= BROTLI_TRANSFORM_OMIT_FIRST_9) {
253
0
      int skip = t - (BROTLI_TRANSFORM_OMIT_FIRST_1 - 1);
254
0
      word += skip;
255
0
      len -= skip;
256
0
    }
257
0
    while (i < len) { dst[idx++] = word[i++]; }
258
0
    if (t == BROTLI_TRANSFORM_UPPERCASE_FIRST) {
259
0
      ToUpperCase(&dst[idx - len]);
260
0
    } else if (t == BROTLI_TRANSFORM_UPPERCASE_ALL) {
261
0
      uint8_t* uppercase = &dst[idx - len];
262
0
      while (len > 0) {
263
0
        int step = ToUpperCase(uppercase);
264
0
        uppercase += step;
265
0
        len -= step;
266
0
      }
267
0
    } else if (t == BROTLI_TRANSFORM_SHIFT_FIRST) {
268
0
      uint16_t param = (uint16_t)(transforms->params[transform_idx * 2]
269
0
          + (transforms->params[transform_idx * 2 + 1] << 8u));
270
0
      Shift(&dst[idx - len], len, param);
271
0
    } else if (t == BROTLI_TRANSFORM_SHIFT_ALL) {
272
0
      uint16_t param = (uint16_t)(transforms->params[transform_idx * 2]
273
0
          + (transforms->params[transform_idx * 2 + 1] << 8u));
274
0
      uint8_t* shift = &dst[idx - len];
275
0
      while (len > 0) {
276
0
        int step = Shift(shift, len, param);
277
0
        shift += step;
278
0
        len -= step;
279
0
      }
280
0
    }
281
0
  }
282
0
  {
283
0
    int suffix_len = *suffix++;
284
0
    while (suffix_len--) { dst[idx++] = *suffix++; }
285
0
    return idx;
286
0
  }
287
0
}
288
289
#if defined(__cplusplus) || defined(c_plusplus)
290
}  /* extern "C" */
291
#endif