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 */
27int 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
129int 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