1 | /* |
2 | * Xor Based Zero Run Length Encoding |
3 | * |
4 | * Copyright 2013 Red Hat, Inc. and/or its affiliates |
5 | * |
6 | * Authors: |
7 | * Orit Wasserman <owasserm@redhat.com> |
8 | * |
9 | * This work is licensed under the terms of the GNU GPL, version 2 or later. |
10 | * See the COPYING file in the top-level directory. |
11 | * |
12 | */ |
13 | #include "qemu/osdep.h" |
14 | #include "qemu/cutils.h" |
15 | #include "xbzrle.h" |
16 | |
17 | /* |
18 | page = zrun nzrun |
19 | | zrun nzrun page |
20 | |
21 | zrun = length |
22 | |
23 | nzrun = length byte... |
24 | |
25 | length = uleb128 encoded integer |
26 | */ |
27 | int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen, |
28 | uint8_t *dst, int dlen) |
29 | { |
30 | uint32_t zrun_len = 0, nzrun_len = 0; |
31 | int d = 0, i = 0; |
32 | long res; |
33 | uint8_t *nzrun_start = NULL; |
34 | |
35 | g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) % |
36 | sizeof(long))); |
37 | |
38 | while (i < slen) { |
39 | /* overflow */ |
40 | if (d + 2 > dlen) { |
41 | return -1; |
42 | } |
43 | |
44 | /* not aligned to sizeof(long) */ |
45 | res = (slen - i) % sizeof(long); |
46 | while (res && old_buf[i] == new_buf[i]) { |
47 | zrun_len++; |
48 | i++; |
49 | res--; |
50 | } |
51 | |
52 | /* word at a time for speed */ |
53 | if (!res) { |
54 | while (i < slen && |
55 | (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { |
56 | i += sizeof(long); |
57 | zrun_len += sizeof(long); |
58 | } |
59 | |
60 | /* go over the rest */ |
61 | while (i < slen && old_buf[i] == new_buf[i]) { |
62 | zrun_len++; |
63 | i++; |
64 | } |
65 | } |
66 | |
67 | /* buffer unchanged */ |
68 | if (zrun_len == slen) { |
69 | return 0; |
70 | } |
71 | |
72 | /* skip last zero run */ |
73 | if (i == slen) { |
74 | return d; |
75 | } |
76 | |
77 | d += uleb128_encode_small(dst + d, zrun_len); |
78 | |
79 | zrun_len = 0; |
80 | nzrun_start = new_buf + i; |
81 | |
82 | /* overflow */ |
83 | if (d + 2 > dlen) { |
84 | return -1; |
85 | } |
86 | /* not aligned to sizeof(long) */ |
87 | res = (slen - i) % sizeof(long); |
88 | while (res && old_buf[i] != new_buf[i]) { |
89 | i++; |
90 | nzrun_len++; |
91 | res--; |
92 | } |
93 | |
94 | /* word at a time for speed, use of 32-bit long okay */ |
95 | if (!res) { |
96 | /* truncation to 32-bit long okay */ |
97 | unsigned long mask = (unsigned long)0x0101010101010101ULL; |
98 | while (i < slen) { |
99 | unsigned long xor; |
100 | xor = *(unsigned long *)(old_buf + i) |
101 | ^ *(unsigned long *)(new_buf + i); |
102 | if ((xor - mask) & ~xor & (mask << 7)) { |
103 | /* found the end of an nzrun within the current long */ |
104 | while (old_buf[i] != new_buf[i]) { |
105 | nzrun_len++; |
106 | i++; |
107 | } |
108 | break; |
109 | } else { |
110 | i += sizeof(long); |
111 | nzrun_len += sizeof(long); |
112 | } |
113 | } |
114 | } |
115 | |
116 | d += uleb128_encode_small(dst + d, nzrun_len); |
117 | /* overflow */ |
118 | if (d + nzrun_len > dlen) { |
119 | return -1; |
120 | } |
121 | memcpy(dst + d, nzrun_start, nzrun_len); |
122 | d += nzrun_len; |
123 | nzrun_len = 0; |
124 | } |
125 | |
126 | return d; |
127 | } |
128 | |
129 | int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen) |
130 | { |
131 | int i = 0, d = 0; |
132 | int ret; |
133 | uint32_t count = 0; |
134 | |
135 | while (i < slen) { |
136 | |
137 | /* zrun */ |
138 | if ((slen - i) < 2) { |
139 | return -1; |
140 | } |
141 | |
142 | ret = uleb128_decode_small(src + i, &count); |
143 | if (ret < 0 || (i && !count)) { |
144 | return -1; |
145 | } |
146 | i += ret; |
147 | d += count; |
148 | |
149 | /* overflow */ |
150 | if (d > dlen) { |
151 | return -1; |
152 | } |
153 | |
154 | /* nzrun */ |
155 | if ((slen - i) < 2) { |
156 | return -1; |
157 | } |
158 | |
159 | ret = uleb128_decode_small(src + i, &count); |
160 | if (ret < 0 || !count) { |
161 | return -1; |
162 | } |
163 | i += ret; |
164 | |
165 | /* overflow */ |
166 | if (d + count > dlen || i + count > slen) { |
167 | return -1; |
168 | } |
169 | |
170 | memcpy(dst + d, src + i, count); |
171 | d += count; |
172 | i += count; |
173 | } |
174 | |
175 | return d; |
176 | } |
177 | |