qemu

FORK: QEMU emulator
git clone https://git.neptards.moe/neptards/qemu.git
Log | Files | Refs | Submodules | LICENSE

xbzrle.c (4179B)

      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 }