]> git.proxmox.com Git - mirror_qemu.git/blob - xbzrle.c
target-ppc: Altivec 2.07: Vector Doubleword Rotate and Shift Instructions
[mirror_qemu.git] / xbzrle.c
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 }