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 } 176