Subject: [rohc] COPY-OFFSET cycles

From: Adam Roach <[email-masked]>
Date: Mon, 5 Aug 2002 17:28:18 -0500

I think Carsten brought this point up before, but I can't seem to find
it in the archives anywhere. And it has just fallen on the floor.

And I cannot overstate its importance.

COPY-OFFSET is defined to take (1 + length + offset) cycles to execute.
In terms of real processing power required to effect this opcode,
though, it's more on the order of (1 + length) -- the memory position
that offset resolves to can be calculated in constant time.

This is creating a very real problem.

Consider an implementation of deflate using a 32k buffer. We send a
compressed message that has 226 bytes (or 1808 bits) of input. At
the maximum value -- 128 cycles per bit -- this leaves us 128000 + 
231424 = 359424 cycles.

In the course of decompressing this message, we can come across a set
of distance/length values like this:

offset = 30709; length = 7
offset = 30633; length = 14
offset = 30432; length = 3
offset = 30696; length = 5
offset = 30572; length = 3
offset = 30571; length = 3
offset = 30699; length = 12
offset = 34; length = 5
offset = 30425; length = 16
offset = 30490; length = 3
offset = 97; length = 14
offset = 30; length = 3
offset = 30699; length = 10
offset = 30565; length = 5
offset = 31; length = 10
offset = 158; length = 3
offset = 104; length = 3
offset = 30667; length = 3

If you add these together to figure out how many cycles just the
"COPY-OFFSET" opcodes are taking here, without any regard for the
rest of the code, you'll get 367734, which exceeds 359424 quite
handily.

And with cycles-per-bit less than 128, you can imagine it only gets
worse.

As you have probably already surmised, these numbers are not
theoretical; they're actual numbers gleaned from our testing of
our SigComp library. This is a real problem that we're seeing.
Worst of all, this particular message is only about 2/3rds of
the way done decoding. We'd need to crank cycles-per-bit up to
256 in order to correctly decompress this message.

On the other hand, if we weight COPY-OFFSET according to its
actual execution time, we can use a cycles-per-bit value of
16 and still burn only 8% of the cycles we're allocated.

I think this is a critical enough error -- and simple enough to
fix -- that it warrants a tweak before RFC publication. We need
to change Figure 11 so that it defines COPY-OFFSET to take (1 + length)
cycles, not (1 + offset + length) cycles; otherwise, we severely limit
the usefulness of SigComp for implementing deflate.

/a

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: "Price, Richard" <[email-masked]>
Date: Wed, 7 Aug 2002 13:00:31 +0100

Hi,

Carsten noticed this mistake a while back but we must have forgotten
to fix it in the draft. We should certainly correct it before the
RFC is published - I'd argue that this ok because we agreed to make
the change before last call, but didn't get round to it.

In the meantime, it's possible to hack round the bug by replacing
the COPY-OFFSET instruction in DEFLATE with the following:

SUBTRACT ($index, $distance_value)
ADD ($index, overflow)
REMAINDER ($index, buffer_size)
ADD ($index, circular_buffer)
COPY-LITERAL ($index, $length_value, $decompressed_pointer)

; define these at the end of the bytecode to avoid forward-referencing:

:buffer_size = udvm_memory_size - circular_buffer
:overflow = buffer_size - circular_buffer

It's messy but it works!

Regards,

Richard

> -----Original Message-----
> From: Adam Roach [mailto:[email-masked]]
> Sent: Monday, August 05, 2002 11:28 PM
> To: Price, Richard; [email-masked]'
> Cc: [email-masked]'
> Subject: COPY-OFFSET cycles
> 
>