root / xbzrle.c @ 29b358f9
History | View | Annotate | Download (4 kB)
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-common.h" |
14 |
#include "include/migration/migration.h" |
15 |
|
16 |
/*
|
17 |
page = zrun nzrun
|
18 |
| zrun nzrun page
|
19 |
|
20 |
zrun = length
|
21 |
|
22 |
nzrun = length byte...
|
23 |
|
24 |
length = uleb128 encoded integer
|
25 |
*/
|
26 |
int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen, |
27 |
uint8_t *dst, int dlen)
|
28 |
{ |
29 |
uint32_t zrun_len = 0, nzrun_len = 0; |
30 |
int d = 0, i = 0; |
31 |
long res, xor;
|
32 |
uint8_t *nzrun_start = NULL;
|
33 |
|
34 |
g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) % |
35 |
sizeof(long))); |
36 |
|
37 |
while (i < slen) {
|
38 |
/* overflow */
|
39 |
if (d + 2 > dlen) { |
40 |
return -1; |
41 |
} |
42 |
|
43 |
/* not aligned to sizeof(long) */
|
44 |
res = (slen - i) % sizeof(long); |
45 |
while (res && old_buf[i] == new_buf[i]) {
|
46 |
zrun_len++; |
47 |
i++; |
48 |
res--; |
49 |
} |
50 |
|
51 |
/* word at a time for speed */
|
52 |
if (!res) {
|
53 |
while (i < slen &&
|
54 |
(*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { |
55 |
i += sizeof(long); |
56 |
zrun_len += sizeof(long); |
57 |
} |
58 |
|
59 |
/* go over the rest */
|
60 |
while (i < slen && old_buf[i] == new_buf[i]) {
|
61 |
zrun_len++; |
62 |
i++; |
63 |
} |
64 |
} |
65 |
|
66 |
/* buffer unchanged */
|
67 |
if (zrun_len == slen) {
|
68 |
return 0; |
69 |
} |
70 |
|
71 |
/* skip last zero run */
|
72 |
if (i == slen) {
|
73 |
return d;
|
74 |
} |
75 |
|
76 |
d += uleb128_encode_small(dst + d, zrun_len); |
77 |
|
78 |
zrun_len = 0;
|
79 |
nzrun_start = new_buf + i; |
80 |
|
81 |
/* overflow */
|
82 |
if (d + 2 > dlen) { |
83 |
return -1; |
84 |
} |
85 |
/* not aligned to sizeof(long) */
|
86 |
res = (slen - i) % sizeof(long); |
87 |
while (res && old_buf[i] != new_buf[i]) {
|
88 |
i++; |
89 |
nzrun_len++; |
90 |
res--; |
91 |
} |
92 |
|
93 |
/* word at a time for speed, use of 32-bit long okay */
|
94 |
if (!res) {
|
95 |
/* truncation to 32-bit long okay */
|
96 |
long mask = (long)0x0101010101010101ULL; |
97 |
while (i < slen) {
|
98 |
xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i); |
99 |
if ((xor - mask) & ~xor & (mask << 7)) { |
100 |
/* found the end of an nzrun within the current long */
|
101 |
while (old_buf[i] != new_buf[i]) {
|
102 |
nzrun_len++; |
103 |
i++; |
104 |
} |
105 |
break;
|
106 |
} else {
|
107 |
i += sizeof(long); |
108 |
nzrun_len += sizeof(long); |
109 |
} |
110 |
} |
111 |
} |
112 |
|
113 |
d += uleb128_encode_small(dst + d, nzrun_len); |
114 |
/* overflow */
|
115 |
if (d + nzrun_len > dlen) {
|
116 |
return -1; |
117 |
} |
118 |
memcpy(dst + d, nzrun_start, nzrun_len); |
119 |
d += nzrun_len; |
120 |
nzrun_len = 0;
|
121 |
} |
122 |
|
123 |
return d;
|
124 |
} |
125 |
|
126 |
int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen) |
127 |
{ |
128 |
int i = 0, d = 0; |
129 |
int ret;
|
130 |
uint32_t count = 0;
|
131 |
|
132 |
while (i < slen) {
|
133 |
|
134 |
/* zrun */
|
135 |
if ((slen - i) < 2) { |
136 |
return -1; |
137 |
} |
138 |
|
139 |
ret = uleb128_decode_small(src + i, &count); |
140 |
if (ret < 0 || (i && !count)) { |
141 |
return -1; |
142 |
} |
143 |
i += ret; |
144 |
d += count; |
145 |
|
146 |
/* overflow */
|
147 |
if (d > dlen) {
|
148 |
return -1; |
149 |
} |
150 |
|
151 |
/* nzrun */
|
152 |
if ((slen - i) < 2) { |
153 |
return -1; |
154 |
} |
155 |
|
156 |
ret = uleb128_decode_small(src + i, &count); |
157 |
if (ret < 0 || !count) { |
158 |
return -1; |
159 |
} |
160 |
i += ret; |
161 |
|
162 |
/* overflow */
|
163 |
if (d + count > dlen || i + count > slen) {
|
164 |
return -1; |
165 |
} |
166 |
|
167 |
memcpy(dst + d, src + i, count); |
168 |
d += count; |
169 |
i += count; |
170 |
} |
171 |
|
172 |
return d;
|
173 |
} |