LXR 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/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 */
  27int 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
 129int 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}
 177