| Message ID | 1325604879-15862-3-git-send-email-owasserm@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 01/03/2012 09:34 AM, Orit Wasserman wrote: > Signed-off-by: Orit Wasserman<owasserm@redhat.com> > --- > arch_init.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 files changed, 58 insertions(+), 0 deletions(-) > > diff --git a/arch_init.c b/arch_init.c > index fdda277..426b34d 100644 > --- a/arch_init.c > +++ b/arch_init.c > @@ -139,6 +139,9 @@ typedef struct XBRLEHeader { > uint32_t xh_cksum; > } XBRLEHeader; > > +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen); > +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen); > + > /***********************************************************/ > /* XBRLE page cache implementation */ > static CacheItem *cache_item_get(unsigned long pos, int item) > @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata) > it->it_addr = addr; > } > > +/* XBRLE (Xor Based Run-Length Encoding) */ > +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen) > +{ > + int d = 0, ch_run = 0, i; > + uint8_t prev = 0, ch = 0; > + > + for (i = 0; i<= slen; i++) { > + if (i != slen) { > + ch = src[i]; > + } > + > + if (!i || (i != slen&& ch == prev&& ch_run< 255)) { > + ch_run++; > + } else { > + if (d+2> dlen) { > + return -1; > + } > + *dst++ = ch_run; > + *dst++ = prev; > + d += 2; > + ch_run = 1; > + } > + > + prev = ch; > + } > + return d; > +} > + > +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen) > +{ > + int d = 0, s; > + > + for (s = 0; s< slen-1; s += 2) { > + uint8_t ch_run = src[s]; > + uint8_t ch = src[s+1]; > + while (ch_run--) { > + if (d == dlen) { > + return -1; > + } > + dst[d] = ch; > + d++; > + } > + } > + return d; > +} > + > +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2) > +{ > + int i; > + > + for (i = 0; i< TARGET_PAGE_SIZE; i++) { > + dst[i] = src1[i] ^ src2[i]; > + } > +} > + I don't think any of these need to be in arch_init.c. It would be nicer to make a xbzrle.c file for this stuff. Regards, Anthony Liguori > static int is_dup_page(uint8_t *page, uint8_t ch) > { > uint32_t val = ch<< 24 | ch<< 16 | ch<< 8 | ch;
On 01/03/2012 09:57 PM, Anthony Liguori wrote: > On 01/03/2012 09:34 AM, Orit Wasserman wrote: >> Signed-off-by: Orit Wasserman<owasserm@redhat.com> >> --- >> arch_init.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ >> 1 files changed, 58 insertions(+), 0 deletions(-) >> >> diff --git a/arch_init.c b/arch_init.c >> index fdda277..426b34d 100644 >> --- a/arch_init.c >> +++ b/arch_init.c >> @@ -139,6 +139,9 @@ typedef struct XBRLEHeader { >> uint32_t xh_cksum; >> } XBRLEHeader; >> >> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen); >> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen); >> + >> /***********************************************************/ >> /* XBRLE page cache implementation */ >> static CacheItem *cache_item_get(unsigned long pos, int item) >> @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata) >> it->it_addr = addr; >> } >> >> +/* XBRLE (Xor Based Run-Length Encoding) */ >> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen) >> +{ >> + int d = 0, ch_run = 0, i; >> + uint8_t prev = 0, ch = 0; >> + >> + for (i = 0; i<= slen; i++) { >> + if (i != slen) { >> + ch = src[i]; >> + } >> + >> + if (!i || (i != slen&& ch == prev&& ch_run< 255)) { >> + ch_run++; >> + } else { >> + if (d+2> dlen) { >> + return -1; >> + } >> + *dst++ = ch_run; >> + *dst++ = prev; >> + d += 2; >> + ch_run = 1; >> + } >> + >> + prev = ch; >> + } >> + return d; >> +} >> + >> +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen) >> +{ >> + int d = 0, s; >> + >> + for (s = 0; s< slen-1; s += 2) { >> + uint8_t ch_run = src[s]; >> + uint8_t ch = src[s+1]; >> + while (ch_run--) { >> + if (d == dlen) { >> + return -1; >> + } >> + dst[d] = ch; >> + d++; >> + } >> + } >> + return d; >> +} >> + >> +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2) >> +{ >> + int i; >> + >> + for (i = 0; i< TARGET_PAGE_SIZE; i++) { >> + dst[i] = src1[i] ^ src2[i]; >> + } >> +} >> + > > I don't think any of these need to be in arch_init.c. It would be nicer to make a xbzrle.c file for this stuff. > I will fix it. > Regards, > > Anthony Liguori > >> static int is_dup_page(uint8_t *page, uint8_t ch) >> { >> uint32_t val = ch<< 24 | ch<< 16 | ch<< 8 | ch; > >
On 01/03/2012 05:34 PM, Orit Wasserman wrote: > > +/* XBRLE (Xor Based Run-Length Encoding) */ > +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen) > +{ > + int d = 0, ch_run = 0, i; > + uint8_t prev = 0, ch = 0; > + > + for (i = 0; i <= slen; i++) { > + if (i != slen) { > + ch = src[i]; > + } > + > + if (!i || (i != slen && ch == prev && ch_run < 255)) { > + ch_run++; > + } else { > + if (d+2 > dlen) { > + return -1; > + } > + *dst++ = ch_run; > + *dst++ = prev; > + d += 2; > + ch_run = 1; > + } > + > + prev = ch; > + } > + return d; > +} > + I think we should specialize this for out case, where we expect runs of zeros (so no need to encode the repeated byte) and runs of non-repeating nonzeros. I propose this encoding: page = zrun | zrun nzrun | zrun nzrun page zrun = length nzrun = length byte... length = uleb128 encoded integer take for example a xor-encoded page: { 1000*0, 1, 2, 3, 4, 3092*0 } representing a page that had a single 32-bit write in the middle. The current encoding would generate ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff 00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00 while the zrle encoding generates e8 07 04 01 02 03 04 94 18 (e8 07 = uleb128 encoding for 1000)
On Wed, Jan 4, 2012 at 12:59 PM, Avi Kivity <avi@redhat.com> wrote: > On 01/03/2012 05:34 PM, Orit Wasserman wrote: >> >> +/* XBRLE (Xor Based Run-Length Encoding) */ >> +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen) >> +{ >> + int d = 0, ch_run = 0, i; >> + uint8_t prev = 0, ch = 0; >> + >> + for (i = 0; i <= slen; i++) { >> + if (i != slen) { >> + ch = src[i]; >> + } >> + >> + if (!i || (i != slen && ch == prev && ch_run < 255)) { >> + ch_run++; >> + } else { >> + if (d+2 > dlen) { >> + return -1; >> + } >> + *dst++ = ch_run; >> + *dst++ = prev; >> + d += 2; >> + ch_run = 1; >> + } >> + >> + prev = ch; >> + } >> + return d; >> +} >> + > > I think we should specialize this for out case, where we expect runs of > zeros (so no need to encode the repeated byte) and runs of non-repeating > nonzeros. I propose this encoding: > > page = zrun > | zrun nzrun > | zrun nzrun page > > zrun = length > > nzrun = length byte... > > length = uleb128 encoded integer > > take for example a xor-encoded page: > > { 1000*0, 1, 2, 3, 4, 3092*0 } > > representing a page that had a single 32-bit write in the middle. The > current encoding would generate > > ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff > 00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00 > > while the zrle encoding generates > > e8 07 04 01 02 03 04 94 18 > > (e8 07 = uleb128 encoding for 1000) Had to look up the Unsigned Little-Endian Base 128 encoding, but it's a nice idea and simple to implement (though we probably want to constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want arbitrarily long integers). http://en.wikipedia.org/wiki/LEB128 Stefan
On 01/04/2012 03:35 PM, Stefan Hajnoczi wrote: > > I think we should specialize this for out case, where we expect runs of > > zeros (so no need to encode the repeated byte) and runs of non-repeating > > nonzeros. I propose this encoding: > > > > page = zrun > > | zrun nzrun > > | zrun nzrun page > > > > zrun = length > > > > nzrun = length byte... > > > > length = uleb128 encoded integer > > > > take for example a xor-encoded page: > > > > { 1000*0, 1, 2, 3, 4, 3092*0 } > > > > representing a page that had a single 32-bit write in the middle. The > > current encoding would generate > > > > ff 00 ff 00 ff 00 eb 00 01 01 01 02 01 03 01 04 ff 00 ff 00 ff 00 ff > > 00 ff 00 ff 00ff 00 ff 00 ff 00 ff 00 ff 00 ff 00 20 00 > > > > while the zrle encoding generates > > > > e8 07 04 01 02 03 04 94 18 > > > > (e8 07 = uleb128 encoding for 1000) > > Had to look up the Unsigned Little-Endian Base 128 encoding, but it's > a nice idea and simple to implement (though we probably want to > constrain ULEB128 to max 32-bit or 64-bit in practice; we don't want > arbitrarily long integers). > > http://en.wikipedia.org/wiki/LEB128 > Sorry, should have provided the URL. And yes, for this use we're limited to TARGET_PAGE_BITS, so having 13-bit encoders/decoders would suffice: int uleb128_encode_small(uint8_t *out, uint32_t n) { if (n < 0x80) { *out++ = n; return 1; } else { *out++ = (n & 0x7f) | 0x80; *out++ = n >> 7; } } int uleb128_decode_small(const uint128 *in, uint32_t *n) { if (!(*in & 0x80)) { *n = *in++; return 1; } else { *n = *in++ & 0x7f; *n |= *in++ << 7; return 2; } }
On 01/04/2012 10:31 AM, Orit Wasserman wrote: >> > I don't think any of these need to be in arch_init.c. It would be nicer to make a xbzrle.c file for this stuff. >> > > I will fix it. > Or just move everything migration-related from arch_init.c to saveram.c. Paolo
diff --git a/arch_init.c b/arch_init.c index fdda277..426b34d 100644 --- a/arch_init.c +++ b/arch_init.c @@ -139,6 +139,9 @@ typedef struct XBRLEHeader { uint32_t xh_cksum; } XBRLEHeader; +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen); +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen); + /***********************************************************/ /* XBRLE page cache implementation */ static CacheItem *cache_item_get(unsigned long pos, int item) @@ -277,6 +280,61 @@ static void cache_insert(unsigned long addr, uint8_t *pdata) it->it_addr = addr; } +/* XBRLE (Xor Based Run-Length Encoding) */ +static int rle_encode(uint8_t *src, int slen, uint8_t *dst, int dlen) +{ + int d = 0, ch_run = 0, i; + uint8_t prev = 0, ch = 0; + + for (i = 0; i <= slen; i++) { + if (i != slen) { + ch = src[i]; + } + + if (!i || (i != slen && ch == prev && ch_run < 255)) { + ch_run++; + } else { + if (d+2 > dlen) { + return -1; + } + *dst++ = ch_run; + *dst++ = prev; + d += 2; + ch_run = 1; + } + + prev = ch; + } + return d; +} + +static int rle_decode(uint8_t *src, int slen, uint8_t *dst, int dlen) +{ + int d = 0, s; + + for (s = 0; s < slen-1; s += 2) { + uint8_t ch_run = src[s]; + uint8_t ch = src[s+1]; + while (ch_run--) { + if (d == dlen) { + return -1; + } + dst[d] = ch; + d++; + } + } + return d; +} + +static void xor_encode(uint8_t *dst, uint8_t *src1, uint8_t *src2) +{ + int i; + + for (i = 0; i < TARGET_PAGE_SIZE; i++) { + dst[i] = src1[i] ^ src2[i]; + } +} + static int is_dup_page(uint8_t *page, uint8_t ch) { uint32_t val = ch << 24 | ch << 16 | ch << 8 | ch;
Signed-off-by: Orit Wasserman <owasserm@redhat.com> --- arch_init.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 58 insertions(+), 0 deletions(-)