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-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 */
  26int 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
 128int 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