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/osdep.h"
  14 #include "qemu/cutils.h"
  15 #include "xbzrle.h"
  16
  17 /*
  18   page = zrun nzrun
  19        | zrun nzrun page
  20
  21   zrun = length
  22
  23   nzrun = length byte...
  24
  25   length = uleb128 encoded integer
  26  */
  27 int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
  28                          uint8_t *dst, int dlen)
  29 {
  30     uint32_t zrun_len = 0, nzrun_len = 0;
  31     int d = 0, i = 0;
  32     long res;
  33     uint8_t *nzrun_start = NULL;
  34
  35     g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
  36                sizeof(long)));
  37
  38     while (i < slen) {
  39         /* overflow */
  40         if (d + 2 > dlen) {
  41             return -1;
  42         }
  43
  44         /* not aligned to sizeof(long) */
  45         res = (slen - i) % sizeof(long);
  46         while (res && old_buf[i] == new_buf[i]) {
  47             zrun_len++;
  48             i++;
  49             res--;
  50         }
  51
  52         /* word at a time for speed */
  53         if (!res) {
  54             while (i < slen &&
  55                    (*(long *)(old_buf + i)) == (*(long *)(new_buf + i))) {
  56                 i += sizeof(long);
  57                 zrun_len += sizeof(long);
  58             }
  59
  60             /* go over the rest */
  61             while (i < slen && old_buf[i] == new_buf[i]) {
  62                 zrun_len++;
  63                 i++;
  64             }
  65         }
  66
  67         /* buffer unchanged */
  68         if (zrun_len == slen) {
  69             return 0;
  70         }
  71
  72         /* skip last zero run */
  73         if (i == slen) {
  74             return d;
  75         }
  76
  77         d += uleb128_encode_small(dst + d, zrun_len);
  78
  79         zrun_len = 0;
  80         nzrun_start = new_buf + i;
  81
  82         /* overflow */
  83         if (d + 2 > dlen) {
  84             return -1;
  85         }
  86         /* not aligned to sizeof(long) */
  87         res = (slen - i) % sizeof(long);
  88         while (res && old_buf[i] != new_buf[i]) {
  89             i++;
  90             nzrun_len++;
  91             res--;
  92         }
  93
  94         /* word at a time for speed, use of 32-bit long okay */
  95         if (!res) {
  96             /* truncation to 32-bit long okay */
  97             unsigned long mask = (unsigned long)0x0101010101010101ULL;
  98             while (i < slen) {
  99                 unsigned long xor;
 100                 xor = *(unsigned long *)(old_buf + i)
 101                     ^ *(unsigned long *)(new_buf + i);
 102                 if ((xor - mask) & ~xor & (mask << 7)) {
 103                     /* found the end of an nzrun within the current long */
 104                     while (old_buf[i] != new_buf[i]) {
 105                         nzrun_len++;
 106                         i++;
 107                     }
 108                     break;
 109                 } else {
 110                     i += sizeof(long);
 111                     nzrun_len += sizeof(long);
 112                 }
 113             }
 114         }
 115
 116         d += uleb128_encode_small(dst + d, nzrun_len);
 117         /* overflow */
 118         if (d + nzrun_len > dlen) {
 119             return -1;
 120         }
 121         memcpy(dst + d, nzrun_start, nzrun_len);
 122         d += nzrun_len;
 123         nzrun_len = 0;
 124     }
 125
 126     return d;
 127 }
 128
 129 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen)
 130 {
 131     int i = 0, d = 0;
 132     int ret;
 133     uint32_t count = 0;
 134
 135     while (i < slen) {
 136
 137         /* zrun */
 138         if ((slen - i) < 2) {
 139             return -1;
 140         }
 141
 142         ret = uleb128_decode_small(src + i, &count);
 143         if (ret < 0 || (i && !count)) {
 144             return -1;
 145         }
 146         i += ret;
 147         d += count;
 148
 149         /* overflow */
 150         if (d > dlen) {
 151             return -1;
 152         }
 153
 154         /* nzrun */
 155         if ((slen - i) < 2) {
 156             return -1;
 157         }
 158
 159         ret = uleb128_decode_small(src + i, &count);
 160         if (ret < 0 || !count) {
 161             return -1;
 162         }
 163         i += ret;
 164
 165         /* overflow */
 166         if (d + count > dlen || i + count > slen) {
 167             return -1;
 168         }
 169
 170         memcpy(dst + d, src + i, count);
 171         d += count;
 172         i += count;
 173     }
 174
 175     return d;
 176 }