These changes are a raw update to a vanilla kernel 4.1.10, with the
[kvmfornfv.git] / qemu / migration / 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;
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             unsigned long mask = (unsigned long)0x0101010101010101ULL;
97             while (i < slen) {
98                 unsigned long xor;
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]) {
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
128 int 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 }