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 }