2 * Xor Based Zero Run Length Encoding
4 * Copyright 2013 Red Hat, Inc. and/or its affiliates
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"
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;
32 uint8_t *nzrun_start = NULL;
34 g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
43 /* not aligned to sizeof(long) */
44 res = (slen - i) % sizeof(long);
45 while (res && old_buf[i] == new_buf[i]) {
51 /* word at a time for speed */
54 (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
56 zrun_len += sizeof(long);
59 /* go over the rest */
60 while (i < slen && old_buf[i] == new_buf[i]) {
66 /* buffer unchanged */
67 if (zrun_len == slen) {
71 /* skip last zero run */
76 d += uleb128_encode_small(dst + d, zrun_len);
79 nzrun_start = new_buf + i;
85 /* not aligned to sizeof(long) */
86 res = (slen - i) % sizeof(long);
87 while (res && old_buf[i] != new_buf[i]) {
93 /* word at a time for speed, use of 32-bit long okay */
95 /* truncation to 32-bit long okay */
96 unsigned long mask = (unsigned long)0x0101010101010101ULL;
99 xor = *(unsigned long *)(old_buf + i)
100 ^ *(unsigned long *)(new_buf + i);
101 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]) {
110 nzrun_len += sizeof(long);
115 d += uleb128_encode_small(dst + d, nzrun_len);
117 if (d + nzrun_len > dlen) {
120 memcpy(dst + d, nzrun_start, nzrun_len);
128 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
137 if ((slen - i) < 2) {
141 ret = uleb128_decode_small(src + i, &count);
142 if (ret < 0 || (i && !count)) {
154 if ((slen - i) < 2) {
158 ret = uleb128_decode_small(src + i, &count);
159 if (ret < 0 || !count) {
165 if (d + count > dlen || i + count > slen) {
169 memcpy(dst + d, src + i, count);