1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
//! Base85 digit <-> value conversion (spec section 8).
use crate;
use cratevalue_to_char;
pub const POW85_2: u32 = 7225; // 85^2
pub const POW85_3: u32 = 614_125; // 85^3
// 85^4, and the only one of the four that does not fit the fast path: a 32-bit
// magic-number division needs the dividend to stay in 32 bits, and 85^4 leaves
// it. `value_to_5chars_32` splits at 85^2 and 85^3 for that reason, and this
// constant is here for the decoder's group arithmetic rather than for it.
pub const POW85_4: u64 = 52_200_625;
/// Alphabet-N characters for every two-digit base-85 value 0..85^2-1, most
/// significant digit first.
///
/// Entries are pairs rather than a flat array so that reading one is a single
/// indexed load. Only the first 85^2 of them are ever read: 14,450 bytes over
/// 226 cache lines, which is 45 % of a 32 kB L1 -- large enough that "it stays
/// in L1" is worth measuring rather than asserting. Read misses per 2 MB
/// encode, under cachegrind with a 32 kB 8-way L1:
///
/// random bytes 1,010 misses over 4,000,000 reads 0.03 %
/// mixed 1,954 over 2,607,324 0.07 %
/// text 10,886 over 214,564 5.1 %
///
/// So it stays where it carries the encode -- block mode reads it twice per
/// four bytes, and the misses are barely more than the 226 the first pass has
/// to take. Where the encode is mostly passthrough it does get evicted between
/// uses, and that is the row to keep in mind before making it larger: the table
/// is cheap there only because it is read twenty times less often.
///
/// The table is rounded up to a power of two so that an index can be brought
/// into range with a mask.
///
/// That is what pays for the extra 1934 bytes, which are never touched. A
/// remainder the caller has already computed is in range by construction, but
/// nothing in its *type* says so, and the bounds check the compiler then cannot
/// discharge was being paid for with a second division -- 7 instructions on the
/// path that carries every block-mode byte, against 1 for the mask.
///
/// The padding is zero, and that is load-bearing rather than incidental: NUL is
/// not an Alphabet-N character, so an index that somehow left the real range
/// would emit output this project's own decoders reject with
/// `InvalidCharacter`, rather than plausible wrong data. It is what takes the
/// place of the bounds check's panic, so do not tidy it into a "real"
/// character. The same holds for the unused half of `IDENTITY_ASCII`, which the
/// translation loop reaches through `b & 0x7f`.
pub const PAIR_TABLE_LEN: usize = 8192;
/// The mask that brings a two-digit value into [`PAIR_CHARS`]'s range, for the
/// indices that need one -- which is not all of them; see the measurements in
/// [`value_to_5chars_32`].
pub const PAIR_MASK: usize = PAIR_TABLE_LEN - 1;
pub const PAIR_CHARS: = ;
/// [`ALPHABET_N`] padded to 128 entries, for the same reason [`PAIR_CHARS`] is
/// padded to 8192: the middle digit is a remainder below 85, and a mask says so
/// where the division that produced it does not.
pub const DIGIT_CHARS: = ;
/// `Base85DigitsToValue`: combine 5 Alphabet-N digit values (each 0-84)
/// into a single integer, most-significant digit first.
/// `ValueToBase85Digits`: split `value` into 5 Alphabet-N digit values
/// (each 0-84), most-significant digit first. `value` must be `< 85^5`.
/// Converts a value (0..85^5-1, which covers every `u32`) into 5 Alphabet-N
/// characters, most significant digit first.
///
/// The obvious loop -- five rounds of "digit = value % 85; value /= 85" --
/// costs five divisions by a constant, each depending on the one before it.
/// Reading the digits out in pairs needs two divisions and three loads instead,
/// and this is the whole of block mode's arithmetic.
///
/// The two divisions are by 85^2 and 85^3 rather than the more obvious 85^3 and
/// then 85^2 of the remainder, so that neither waits for the other: `value /
/// 85^2` is `head*85 + mid`, because `85^3 = 85 * 85^2`, which recovers the
/// middle digit from a quotient computed in parallel with the head.
/// Same, for the range of values that does not fit in 32 bits: every signal is
/// `2^32 + payload` or above (spec section 9). One signal covers a whole
/// segment -- up to 2048 characters of DP, or up to 2048 bytes of Fill -- so
/// this path is cold and stays the straightforward loop.
/// Encode `value` as a 5-character Alphabet-N string. Used by the tests to build
/// signals by hand; the encoder writes digits straight into its output buffer.
/// Convert 5 already-validated Alphabet-N characters into their combined
/// value. Returns `None` if any character is not in Alphabet-N.
///
/// A fixed-size array rather than a slice: the length is part of the format,
/// the compiler can check it here rather than a `debug_assert!` that a release
/// build drops, and the one caller stops building a `Vec` per five characters
/// to satisfy a slice signature -- on the decoder's error path, which walks a
/// whole rejected stream.