blob: 8e220bf25b9a4002675e4532b48b25ec8b47e9d6 [file] [log] [blame]
Orit Wassermanba2e28e2013-01-31 09:12:15 +02001/*
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 */
26int 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;
Peter Maydell968fc242014-03-28 15:12:57 +000031 long res;
Orit Wassermanba2e28e2013-01-31 09:12:15 +020032 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 */
Peter Maydell968fc242014-03-28 15:12:57 +000096 unsigned long mask = (unsigned long)0x0101010101010101ULL;
Orit Wassermanba2e28e2013-01-31 09:12:15 +020097 while (i < slen) {
Peter Maydell968fc242014-03-28 15:12:57 +000098 unsigned long xor;
99 xor = *(unsigned long *)(old_buf + i)
100 ^ *(unsigned long *)(new_buf + i);
Orit Wassermanba2e28e2013-01-31 09:12:15 +0200101 if ((xor - mask) & ~xor & (mask << 7)) {
102 /* found the end of an nzrun within the current long */
103 while (old_buf[i] != new_buf[i]) {
104 nzrun_len++;
105 i++;
106 }
107 break;
108 } else {
109 i += sizeof(long);
110 nzrun_len += sizeof(long);
111 }
112 }
113 }
114
115 d += uleb128_encode_small(dst + d, nzrun_len);
116 /* overflow */
117 if (d + nzrun_len > dlen) {
118 return -1;
119 }
120 memcpy(dst + d, nzrun_start, nzrun_len);
121 d += nzrun_len;
122 nzrun_len = 0;
123 }
124
125 return d;
126}
127
128int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
129{
130 int i = 0, d = 0;
131 int ret;
132 uint32_t count = 0;
133
134 while (i < slen) {
135
136 /* zrun */
137 if ((slen - i) < 2) {
138 return -1;
139 }
140
141 ret = uleb128_decode_small(src + i, &count);
142 if (ret < 0 || (i && !count)) {
143 return -1;
144 }
145 i += ret;
146 d += count;
147
148 /* overflow */
149 if (d > dlen) {
150 return -1;
151 }
152
153 /* nzrun */
154 if ((slen - i) < 2) {
155 return -1;
156 }
157
158 ret = uleb128_decode_small(src + i, &count);
159 if (ret < 0 || !count) {
160 return -1;
161 }
162 i += ret;
163
164 /* overflow */
165 if (d + count > dlen || i + count > slen) {
166 return -1;
167 }
168
169 memcpy(dst + d, src + i, count);
170 d += count;
171 i += count;
172 }
173
174 return d;
175}