Subject: [rohc] ROHC-FN tutorial: scaled_seq_no compression formula

From: Klaus Warnke <[email-masked]>
Date: Thu, 03 Sep 2009 14:14:23 +0200

Hello RoHC'ers 2.0,

the example B.9. in the RFC 4997 ROHC-FN introduces a scaled_seq_no,
but provides no formula for compression. 

Here is my compression formula, maybe it is helpful for other.

scaled_seq_no.UVALUE = (sequence_no.UVALUE + (m*16)) / 3

where m is:

m = 0 if (U%3 == 0)
m = 2 if (U%3 == 1)
m = 1 if (U%3 == 2)

Checked with oo calc:

U	U%3	m	M*16	U+m*16	C=(U+m*16)/3	C*3	U=(C*3)%16
-       ---     -       ----    ------  ------------    ---     ----------
0	0	0	0	0	0	        0	0
1	1	2	32	33	11	        33	1
2	2	1	16	18	6	        18	2
3	0	0	0	3	1	        3	3
4	1	2	32	36	12	        36	4
5	2	1	16	21	7	        21	5
6	0	0	0	6	2	        6	6
7	1	2	32	39	13	        39	7
8	2	1	16	24	8	        24	8
9	0	0	0	9	3	        9	9
10	1	2	32	42	14	        42	10
11	2	1	16	27	9	        27	11
12	0	0	0	12	4	        12	12
13	1	2	32	45	15	        45	13
14	2	1	16	30	10	        30	14
15	0	0	0	15	5	        15	15

br
Klaus

---

From: Raffles <[email-masked]>
Date: Thu, 03 Sep 2009 21:37:39 +0100

Hi Klaus,

Thanks for the post. I think you have probably already seen the 
following line in the example:

         ENFORCE(sequence_no.UVALUE
                   == (scaled_seq_no.UVALUE * 3) % 16);

Which is to say, a similar function to the one which you have described, 
but expressed in the inverse form. The bindings created by this are two 
way. That is, this single line defines both compression and 
decompression. One of the key principles of the FN is that all bindings 
are two way, so that you only define the profile once for both 
compression and decompression. You specify "what" rather than "how". See 
section 3.2.1 for more details: 
http://tools.ietf.org/html/rfc4997#section-3.2.1

Thanks for taking the time to read the RFC and send in a post.

If you have any questions feel free to ask.

Regards

Raffles

Klaus Warnke wrote:
> _______________________________________________
> Rohc mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rohc
>
>   

-- 
Raffles (Robert Finking)
m: 0789 463 9887
e: [email-masked]
w: gluft.com

         O                  O
 OOOOOO  O  O    O OOOOOO OOOOO
 O    O  O  O    O OOOOO    O
 OOOOOO  O  OOOOOO O        O
 OOOOOO
      we  care  about  software

-----------------------------------------------------------------
Gluft Ltd. Registered No.: 6795336
The information contained in this e-mail and any attachments is
proprietary to Gluft Ltd and must not be passed to any third
party without permission. This communication is for information
only and shall not create or change any contractual relationship.
Please consider the environment before printing. Thank you.
-----------------------------------------------------------------

---

From: Klaus Warnke <[email-masked]>
Date: Fri, 04 Sep 2009 11:39:20 +0200

Hi Raffles,

I tried to implement this encoding:

  ENFORCE(sequence_no.UVALUE == (scaled_seq_no.UVALUE * 3) % 16);

I saw, it is easy to calculate the sequence_no.UVALUE from then
scaled_seq_no.UVALUE, because the formula can be used 1:1.
But if I want to calculate the scaled_seq_no.UVALUE from the
sequence_no.UVALUE, I can't see how here. 

Did I oversaw something?

So I restructured the formula, which was not so easy to me, because
there is no inverse for the "%" operator. So I wanted to share this,
maybe it is helpful for other developers.

> You specify "what" rather than "how"
My intention was to explain "how", not "what".
Could you please explain what was wrong about that?

br
Klaus

At Thu, 03 Sep 2009 21:37:39 +0100,

---

From: Raffles <[email-masked]>
Date: Fri, 04 Sep 2009 22:15:36 +0100

Hi Klaus,

Thanks for the clarification. There is certainly nothing wrong with
designing the "how" rather than the "what" - the main point is to
understand that the FN only intends to specify the "what". This is
intentional, to allow the implementer as much freedom as possible.
Originally we developed an engine which would take an FN description
and automatically provide compression and decompression, meaning that
you could get a reference solution without specifying the "how" part.
However, this was a lot of work to maintain so we abandoned it.

For reference, with real protocols where the operators used are
non-invertible, look-up tables are very useful (and also fast).
Although the individual operators used may be many-to-one as with
modulo, the overall mapping must be one-to-one, so a lookup table is a
nice solution. Of course scalability is an issue - for this example
though the tables are small enough to sit in L1 cache so offer a good
solution. Partly this depends on your architecture, but typically
modulo consumes a lot of clock cycles.

Thanks again for the input.

All the best

Raffles

Klaus Warnke wrote:

Hi Raffles,

Did I oversaw something?

br
Klaus

Hi Klaus,

Regards

Raffles

Klaus Warnke wrote:

Hello RoHC'ers 2.0,

where m is:

m = 0 if (U%3 == 0)
m = 2 if (U%3 == 1)
m = 1 if (U%3 == 2)

Checked with oo calc:

br
Klaus

--
Raffles (Robert Finking)
m: 0789 463 9887
e: [email-masked]
w: gluft.com

O O

--
Raffles (Robert Finking)
m: 0789 463 9887
e: [email-masked]
w: gluft.com

O O

---

From: Klaus Warnke <[email-masked]>
Date: Mon, 07 Sep 2009 11:50:20 +0200

> However, this was a lot of work to maintain so we abandoned it.
I agree...

> modulo consumes a lot of clock cycles.
Thanks, good hint.

br
Klaus

At Fri, 04 Sep 2009 22:15:36 +0100,
Raffles wrote:
> 
> [1  <text/html; ISO-8859-1 (7bit)>]
> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
> <html>
> <head>
>   <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
> </head>
> <body bgcolor="#ffffff" text="#000000">
> Hi Klaus,<br>
> <br>
> However, this was a lot of work to maintain so we abandoned it.<br>
> <br>
> modulo consumes a lot of clock cycles.<br>
> <br>
> Thanks again for the input.<br>
> <br>
> All the best<br>
> <br>
> Raffles<br>
> <br>
> Klaus Warnke wrote:
> <blockquote cite="mid:[email-masked]"
>  type="cite">
>   <pre wrap="">Hi Raffles,
> 
>   </pre>
>   <blockquote type="cite">
>     <pre wrap="">You specify "what" rather than "how"
>     </pre>
>   </blockquote>
>   <pre wrap=""><!---->My intention was to explain "how", not "what".
>   </pre>
>   <blockquote type="cite">
>     <pre wrap="">Hi Klaus,
> <a class="moz-txt-link-freetext" href="http://tools.ietf.org/html/rfc4997#section-3.2.1">http://tools.ietf.org/html/rfc4997#section-3.2.1</a>
> 
>     </pre>
>     <blockquote type="cite">
>       <pre wrap="">Hello RoHC'ers 2.0,
> 
> <a class="moz-txt-link-abbreviated" href="mailto:[email-masked]">[email-masked]</a>
> <a class="moz-txt-link-freetext" href="https://www.ietf.org/mailman/listinfo/rohc">https://www.ietf.org/mailman/listinfo/rohc</a>
> 
>   
>       </pre>
>     </blockquote>
>     <pre wrap="">-- 
> Raffles (Robert Finking)
> m: 0789 463 9887
> e: <a class="moz-txt-link-abbreviated" href="mailto:[email-masked]">[email-masked]</a>
> w: gluft.com
> 
>          O                  O
> <a class="moz-txt-link-abbreviated" href="mailto:[email-masked]">[email-masked]</a>
> <a class="moz-txt-link-freetext" href="https://www.ietf.org/mailman/listinfo/rohc">https://www.ietf.org/mailman/listinfo/rohc</a>
>     </pre>
>   </blockquote>
>   <pre wrap=""><!---->_______________________________________________
> Rohc mailing list
> <a class="moz-txt-link-abbreviated" href="mailto:[email-masked]">[email-masked]</a>
> <a class="moz-txt-link-freetext" href="https://www.ietf.org/mailman/listinfo/rohc">https://www.ietf.org/mailman/listinfo/rohc</a>
> 
>   </pre>
> </blockquote>
> <br>
> <pre class="moz-signature" cols="72">-- 
> Raffles (Robert Finking)
> m: 0789 463 9887
> e: <a class="moz-txt-link-abbreviated" href="mailto:[email-masked]">[email-masked]</a>
> w: gluft.com
> 
>          O                  O
> </pre>
> </body>
> </html>
> [2  <text/plain; us-ascii (7bit)>]