New alphabet for the base85x encoding

Unfortunately it turned out that the base85x encoding proposed in the last post is damn slow. To encode a 400 KB picture from memory to memory, the PHP implementation needs 0.2 seconds and the Java implementation needs 0.1 seconds. That’s only 4 MB/s.

A lot of this time is spent on alphabet table lookups. So I have the hope to be able to reduce the number of lookups. The original base85 just adds 33 to every value 0,…,84 in order to get the right ASCII character. That is fast but leads to all ASCII characters between 33 and 117 including “<” and “>”.

So the question was, what is the simplest function to map 0,…,84 to a subset of the 94 printable ASCII values excluding: < > ” ‘. The best I could find was this one:

In Java I could reduce the encoding time from 0.1 s to 0.075 s by using the following formula instead of a lookup table:

out = (char) ((c1 >= 21) ? c1 + 42 : ((c1 != 0) ? c1 + 39 : 33)));

I think some more enhancements are possible, especially in c/c++ where you can do better binary operations and use unsigned variables.

Overall this leads to the following new base85x encoding alphabet:

0
!
1
(
2
)
3
*
4
+
5
,
6
-
7
.
8
/
9
0
10
1
11
2
12
3
13
4
14
5
15
6
16
7
17
8
18
9
19
:
20
;
21
?
22
@
23
A
24
B
25
C
26
D
27
E
28
F
29
G
30
H
31
I
32
J
33
K
34
L
35
M
36
N
37
O
38
P
39
Q
40
R
41
S
42
T
43
U
44
V
45
W
46
X
47
Y
48
Z
49
[
50
\
51
]
52
^
53
_
54
`
55
a
56
b
57
c
58
d
59
e
60
f
61
g
62
h
63
i
64
j
65
k
66
l
67
m
68
n
69
o
70
p
71
q
72
r
73
s
74
t
75
u
76
v
77
w
78
x
79
y
80
z
81
{
82
|
83
}
84
~

But why is base85 so much slower compared to base64? Well, 64 is a power of 2 (2^6 = 64) which means that a multiplication by 64 is equal to a binary shift of 6 positions to the left and a division by 64 is equal to a right shift of 6 positions. Additionally the modulo operation a%64 is the same as cutting the lower 5 bits of a. All these essential operations are slower in base 85.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.