root / xbzrle.c @ 29b358f9
History | View | Annotate | Download (4 kB)
1 | ba2e28e8 | Orit Wasserman | /*
|
---|---|---|---|
2 | ba2e28e8 | Orit Wasserman | * Xor Based Zero Run Length Encoding
|
3 | ba2e28e8 | Orit Wasserman | *
|
4 | ba2e28e8 | Orit Wasserman | * Copyright 2013 Red Hat, Inc. and/or its affiliates
|
5 | ba2e28e8 | Orit Wasserman | *
|
6 | ba2e28e8 | Orit Wasserman | * Authors:
|
7 | ba2e28e8 | Orit Wasserman | * Orit Wasserman <owasserm@redhat.com>
|
8 | ba2e28e8 | Orit Wasserman | *
|
9 | ba2e28e8 | Orit Wasserman | * This work is licensed under the terms of the GNU GPL, version 2 or later.
|
10 | ba2e28e8 | Orit Wasserman | * See the COPYING file in the top-level directory.
|
11 | ba2e28e8 | Orit Wasserman | *
|
12 | ba2e28e8 | Orit Wasserman | */
|
13 | ba2e28e8 | Orit Wasserman | #include "qemu-common.h" |
14 | ba2e28e8 | Orit Wasserman | #include "include/migration/migration.h" |
15 | ba2e28e8 | Orit Wasserman | |
16 | ba2e28e8 | Orit Wasserman | /*
|
17 | ba2e28e8 | Orit Wasserman | page = zrun nzrun
|
18 | ba2e28e8 | Orit Wasserman | | zrun nzrun page
|
19 | ba2e28e8 | Orit Wasserman | |
20 | ba2e28e8 | Orit Wasserman | zrun = length
|
21 | ba2e28e8 | Orit Wasserman | |
22 | ba2e28e8 | Orit Wasserman | nzrun = length byte...
|
23 | ba2e28e8 | Orit Wasserman | |
24 | ba2e28e8 | Orit Wasserman | length = uleb128 encoded integer
|
25 | ba2e28e8 | Orit Wasserman | */
|
26 | ba2e28e8 | Orit Wasserman | int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen, |
27 | ba2e28e8 | Orit Wasserman | uint8_t *dst, int dlen)
|
28 | ba2e28e8 | Orit Wasserman | { |
29 | ba2e28e8 | Orit Wasserman | uint32_t zrun_len = 0, nzrun_len = 0; |
30 | ba2e28e8 | Orit Wasserman | int d = 0, i = 0; |
31 | ba2e28e8 | Orit Wasserman | long res, xor;
|
32 | ba2e28e8 | Orit Wasserman | uint8_t *nzrun_start = NULL;
|
33 | ba2e28e8 | Orit Wasserman | |
34 | ba2e28e8 | Orit Wasserman | g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) % |
35 | ba2e28e8 | Orit Wasserman | sizeof(long))); |
36 | ba2e28e8 | Orit Wasserman | |
37 | ba2e28e8 | Orit Wasserman | while (i < slen) {
|
38 | ba2e28e8 | Orit Wasserman | /* overflow */
|
39 | ba2e28e8 | Orit Wasserman | if (d + 2 > dlen) { |
40 | ba2e28e8 | Orit Wasserman | return -1; |
41 | ba2e28e8 | Orit Wasserman | } |
42 | ba2e28e8 | Orit Wasserman | |
43 | ba2e28e8 | Orit Wasserman | /* not aligned to sizeof(long) */
|
44 | ba2e28e8 | Orit Wasserman | res = (slen - i) % sizeof(long); |
45 | ba2e28e8 | Orit Wasserman | while (res && old_buf[i] == new_buf[i]) {
|
46 | ba2e28e8 | Orit Wasserman | zrun_len++; |
47 | ba2e28e8 | Orit Wasserman | i++; |
48 | ba2e28e8 | Orit Wasserman | res--; |
49 | ba2e28e8 | Orit Wasserman | } |
50 | ba2e28e8 | Orit Wasserman | |
51 | ba2e28e8 | Orit Wasserman | /* word at a time for speed */
|
52 | ba2e28e8 | Orit Wasserman | if (!res) {
|
53 | ba2e28e8 | Orit Wasserman | while (i < slen &&
|
54 | ba2e28e8 | Orit Wasserman | (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) { |
55 | ba2e28e8 | Orit Wasserman | i += sizeof(long); |
56 | ba2e28e8 | Orit Wasserman | zrun_len += sizeof(long); |
57 | ba2e28e8 | Orit Wasserman | } |
58 | ba2e28e8 | Orit Wasserman | |
59 | ba2e28e8 | Orit Wasserman | /* go over the rest */
|
60 | ba2e28e8 | Orit Wasserman | while (i < slen && old_buf[i] == new_buf[i]) {
|
61 | ba2e28e8 | Orit Wasserman | zrun_len++; |
62 | ba2e28e8 | Orit Wasserman | i++; |
63 | ba2e28e8 | Orit Wasserman | } |
64 | ba2e28e8 | Orit Wasserman | } |
65 | ba2e28e8 | Orit Wasserman | |
66 | ba2e28e8 | Orit Wasserman | /* buffer unchanged */
|
67 | ba2e28e8 | Orit Wasserman | if (zrun_len == slen) {
|
68 | ba2e28e8 | Orit Wasserman | return 0; |
69 | ba2e28e8 | Orit Wasserman | } |
70 | ba2e28e8 | Orit Wasserman | |
71 | ba2e28e8 | Orit Wasserman | /* skip last zero run */
|
72 | ba2e28e8 | Orit Wasserman | if (i == slen) {
|
73 | ba2e28e8 | Orit Wasserman | return d;
|
74 | ba2e28e8 | Orit Wasserman | } |
75 | ba2e28e8 | Orit Wasserman | |
76 | ba2e28e8 | Orit Wasserman | d += uleb128_encode_small(dst + d, zrun_len); |
77 | ba2e28e8 | Orit Wasserman | |
78 | ba2e28e8 | Orit Wasserman | zrun_len = 0;
|
79 | ba2e28e8 | Orit Wasserman | nzrun_start = new_buf + i; |
80 | ba2e28e8 | Orit Wasserman | |
81 | ba2e28e8 | Orit Wasserman | /* overflow */
|
82 | ba2e28e8 | Orit Wasserman | if (d + 2 > dlen) { |
83 | ba2e28e8 | Orit Wasserman | return -1; |
84 | ba2e28e8 | Orit Wasserman | } |
85 | ba2e28e8 | Orit Wasserman | /* not aligned to sizeof(long) */
|
86 | ba2e28e8 | Orit Wasserman | res = (slen - i) % sizeof(long); |
87 | ba2e28e8 | Orit Wasserman | while (res && old_buf[i] != new_buf[i]) {
|
88 | ba2e28e8 | Orit Wasserman | i++; |
89 | ba2e28e8 | Orit Wasserman | nzrun_len++; |
90 | ba2e28e8 | Orit Wasserman | res--; |
91 | ba2e28e8 | Orit Wasserman | } |
92 | ba2e28e8 | Orit Wasserman | |
93 | ba2e28e8 | Orit Wasserman | /* word at a time for speed, use of 32-bit long okay */
|
94 | ba2e28e8 | Orit Wasserman | if (!res) {
|
95 | ba2e28e8 | Orit Wasserman | /* truncation to 32-bit long okay */
|
96 | ba2e28e8 | Orit Wasserman | long mask = (long)0x0101010101010101ULL; |
97 | ba2e28e8 | Orit Wasserman | while (i < slen) {
|
98 | ba2e28e8 | Orit Wasserman | xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i); |
99 | ba2e28e8 | Orit Wasserman | if ((xor - mask) & ~xor & (mask << 7)) { |
100 | ba2e28e8 | Orit Wasserman | /* found the end of an nzrun within the current long */
|
101 | ba2e28e8 | Orit Wasserman | while (old_buf[i] != new_buf[i]) {
|
102 | ba2e28e8 | Orit Wasserman | nzrun_len++; |
103 | ba2e28e8 | Orit Wasserman | i++; |
104 | ba2e28e8 | Orit Wasserman | } |
105 | ba2e28e8 | Orit Wasserman | break;
|
106 | ba2e28e8 | Orit Wasserman | } else {
|
107 | ba2e28e8 | Orit Wasserman | i += sizeof(long); |
108 | ba2e28e8 | Orit Wasserman | nzrun_len += sizeof(long); |
109 | ba2e28e8 | Orit Wasserman | } |
110 | ba2e28e8 | Orit Wasserman | } |
111 | ba2e28e8 | Orit Wasserman | } |
112 | ba2e28e8 | Orit Wasserman | |
113 | ba2e28e8 | Orit Wasserman | d += uleb128_encode_small(dst + d, nzrun_len); |
114 | ba2e28e8 | Orit Wasserman | /* overflow */
|
115 | ba2e28e8 | Orit Wasserman | if (d + nzrun_len > dlen) {
|
116 | ba2e28e8 | Orit Wasserman | return -1; |
117 | ba2e28e8 | Orit Wasserman | } |
118 | ba2e28e8 | Orit Wasserman | memcpy(dst + d, nzrun_start, nzrun_len); |
119 | ba2e28e8 | Orit Wasserman | d += nzrun_len; |
120 | ba2e28e8 | Orit Wasserman | nzrun_len = 0;
|
121 | ba2e28e8 | Orit Wasserman | } |
122 | ba2e28e8 | Orit Wasserman | |
123 | ba2e28e8 | Orit Wasserman | return d;
|
124 | ba2e28e8 | Orit Wasserman | } |
125 | ba2e28e8 | Orit Wasserman | |
126 | ba2e28e8 | Orit Wasserman | int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen) |
127 | ba2e28e8 | Orit Wasserman | { |
128 | ba2e28e8 | Orit Wasserman | int i = 0, d = 0; |
129 | ba2e28e8 | Orit Wasserman | int ret;
|
130 | ba2e28e8 | Orit Wasserman | uint32_t count = 0;
|
131 | ba2e28e8 | Orit Wasserman | |
132 | ba2e28e8 | Orit Wasserman | while (i < slen) {
|
133 | ba2e28e8 | Orit Wasserman | |
134 | ba2e28e8 | Orit Wasserman | /* zrun */
|
135 | ba2e28e8 | Orit Wasserman | if ((slen - i) < 2) { |
136 | ba2e28e8 | Orit Wasserman | return -1; |
137 | ba2e28e8 | Orit Wasserman | } |
138 | ba2e28e8 | Orit Wasserman | |
139 | ba2e28e8 | Orit Wasserman | ret = uleb128_decode_small(src + i, &count); |
140 | ba2e28e8 | Orit Wasserman | if (ret < 0 || (i && !count)) { |
141 | ba2e28e8 | Orit Wasserman | return -1; |
142 | ba2e28e8 | Orit Wasserman | } |
143 | ba2e28e8 | Orit Wasserman | i += ret; |
144 | ba2e28e8 | Orit Wasserman | d += count; |
145 | ba2e28e8 | Orit Wasserman | |
146 | ba2e28e8 | Orit Wasserman | /* overflow */
|
147 | ba2e28e8 | Orit Wasserman | if (d > dlen) {
|
148 | ba2e28e8 | Orit Wasserman | return -1; |
149 | ba2e28e8 | Orit Wasserman | } |
150 | ba2e28e8 | Orit Wasserman | |
151 | ba2e28e8 | Orit Wasserman | /* nzrun */
|
152 | ba2e28e8 | Orit Wasserman | if ((slen - i) < 2) { |
153 | ba2e28e8 | Orit Wasserman | return -1; |
154 | ba2e28e8 | Orit Wasserman | } |
155 | ba2e28e8 | Orit Wasserman | |
156 | ba2e28e8 | Orit Wasserman | ret = uleb128_decode_small(src + i, &count); |
157 | ba2e28e8 | Orit Wasserman | if (ret < 0 || !count) { |
158 | ba2e28e8 | Orit Wasserman | return -1; |
159 | ba2e28e8 | Orit Wasserman | } |
160 | ba2e28e8 | Orit Wasserman | i += ret; |
161 | ba2e28e8 | Orit Wasserman | |
162 | ba2e28e8 | Orit Wasserman | /* overflow */
|
163 | ba2e28e8 | Orit Wasserman | if (d + count > dlen || i + count > slen) {
|
164 | ba2e28e8 | Orit Wasserman | return -1; |
165 | ba2e28e8 | Orit Wasserman | } |
166 | ba2e28e8 | Orit Wasserman | |
167 | ba2e28e8 | Orit Wasserman | memcpy(dst + d, src + i, count); |
168 | ba2e28e8 | Orit Wasserman | d += count; |
169 | ba2e28e8 | Orit Wasserman | i += count; |
170 | ba2e28e8 | Orit Wasserman | } |
171 | ba2e28e8 | Orit Wasserman | |
172 | ba2e28e8 | Orit Wasserman | return d;
|
173 | ba2e28e8 | Orit Wasserman | } |