target-i386: Use mulu2 and muls2
[qemu/pbrook.git] / xbzrle.c
blobfbcb35d0e33ffaf9ea8aedb4c33a32ff5643dd25
1 /*
2 * Xor Based Zero Run Length Encoding
4 * Copyright 2013 Red Hat, Inc. and/or its affiliates
6 * Authors:
7 * Orit Wasserman <owasserm@redhat.com>
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.
13 #include "qemu-common.h"
14 #include "include/migration/migration.h"
17 page = zrun nzrun
18 | zrun nzrun page
20 zrun = length
22 nzrun = length byte...
24 length = uleb128 encoded integer
26 int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
27 uint8_t *dst, int dlen)
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;
34 g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
35 sizeof(long)));
37 while (i < slen) {
38 /* overflow */
39 if (d + 2 > dlen) {
40 return -1;
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--;
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);
59 /* go over the rest */
60 while (i < slen && old_buf[i] == new_buf[i]) {
61 zrun_len++;
62 i++;
66 /* buffer unchanged */
67 if (zrun_len == slen) {
68 return 0;
71 /* skip last zero run */
72 if (i == slen) {
73 return d;
76 d += uleb128_encode_small(dst + d, zrun_len);
78 zrun_len = 0;
79 nzrun_start = new_buf + i;
81 /* overflow */
82 if (d + 2 > dlen) {
83 return -1;
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--;
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++;
105 break;
106 } else {
107 i += sizeof(long);
108 nzrun_len += sizeof(long);
113 d += uleb128_encode_small(dst + d, nzrun_len);
114 /* overflow */
115 if (d + nzrun_len > dlen) {
116 return -1;
118 memcpy(dst + d, nzrun_start, nzrun_len);
119 d += nzrun_len;
120 nzrun_len = 0;
123 return d;
126 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
128 int i = 0, d = 0;
129 int ret;
130 uint32_t count = 0;
132 while (i < slen) {
134 /* zrun */
135 if ((slen - i) < 2) {
136 return -1;
139 ret = uleb128_decode_small(src + i, &count);
140 if (ret < 0 || (i && !count)) {
141 return -1;
143 i += ret;
144 d += count;
146 /* overflow */
147 if (d > dlen) {
148 return -1;
151 /* nzrun */
152 if ((slen - i) < 2) {
153 return -1;
156 ret = uleb128_decode_small(src + i, &count);
157 if (ret < 0 || !count) {
158 return -1;
160 i += ret;
162 /* overflow */
163 if (d + count > dlen || i + count > slen) {
164 return -1;
167 memcpy(dst + d, src + i, count);
168 d += count;
169 i += count;
172 return d;