Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.misc > #5006 > unrolled thread

The 8-Byte Two-Step

Back to article view | Back to comp.misc

Contents

  The 8-Byte Two-Step Rich <rich@example.invalid> - 2014-09-20 20:41 +0000
    Re: The 8-Byte Two-Step Bob Eager <news0002@eager.cx> - 2014-09-20 21:14 +0000
      Re: The 8-Byte Two-Step Marko Rauhamaa <marko@pacujo.net> - 2014-09-21 00:48 +0300
        Re: The 8-Byte Two-Step Bob Eager <news0002@eager.cx> - 2014-09-21 08:27 +0000
          Re: The 8-Byte Two-Step Marko Rauhamaa <marko@pacujo.net> - 2014-09-21 14:14 +0300
            Re: The 8-Byte Two-Step Marko Rauhamaa <marko@pacujo.net> - 2014-09-23 11:19 +0300
            Re: The 8-Byte Two-Step Christian Neukirchen <chneukirchen@gmail.com> - 2014-09-23 18:26 +0200
        Re: The 8-Byte Two-Step mm0fmf <none@mailinator.com> - 2014-09-21 20:45 +0100
    Re: The 8-Byte Two-Step Sylvia Else <sylvia@not.at.this.address> - 2014-09-21 13:42 +1000

#5006 — The 8-Byte Two-Step

http://zinascii.com/2014/the-8-byte-two-step.html

   While studying the Illumos queue implementation I came across a line of
   code that left me quite perplexed.

   #define MQ_ALIGNSIZE 8 /* 64-bit alignment */ ... temp = (mqhp->mq_maxsz
   + MQ_ALIGNSIZE - 1) & ~(MQ_ALIGNSIZE - 1);

   I knew it had something to do with alignment on a 64-bit boundary, but
   just how the hell was it doing it? Why is it subtracting one from the
   alignment size? Why is it negating the expression on the right? Why is
   it adding to the max message size? What the hell is going on?

   At first I attempted to derive the pattern in my head but kept losing my
   place; forced to start over multiple times. After placing my pride on
   the bookshelf next to me, I wrote some C to help decode the mystery. The
   program breaks the expression into its three parts, printing the base-2
   representation of each step. Here are some test runs with different
   sizes:

   ...

[toc] | [next] | [standalone]

#5007

On Sat, 20 Sep 2014 20:41:29 +0000, Rich wrote:

> http://zinascii.com/2014/the-8-byte-two-step.html
> 
>    While studying the Illumos queue implementation I came across a line
>    of code that left me quite perplexed.
> 
>    #define MQ_ALIGNSIZE 8 /* 64-bit alignment */ ... temp =
>    (mqhp->mq_maxsz + MQ_ALIGNSIZE - 1) & ~(MQ_ALIGNSIZE - 1);
> 
>    I knew it had something to do with alignment on a 64-bit boundary,
>    but just how the hell was it doing it? Why is it subtracting one from
>    the alignment size? Why is it negating the expression on the right?
>    Why is it adding to the max message size? What the hell is going on?
> 
>    At first I attempted to derive the pattern in my head but kept losing
>    my place; forced to start over multiple times. After placing my pride
>    on the bookshelf next to me, I wrote some C to help decode the
>    mystery. The program breaks the expression into its three parts,
>    printing the base-2 representation of each step. Here are some test
>    runs with different sizes:
> 
>    ...

Standard bit of code. I can't remember when I didn't know that one!



-- 
Using UNIX since v6 (1975)...

Use the BIG mirror service in the UK:
 http://www.mirrorservice.org

[toc] | [prev] | [next] | [standalone]

#5008

Bob Eager <news0002@eager.cx>:

>>    (mqhp->mq_maxsz + MQ_ALIGNSIZE - 1) & ~(MQ_ALIGNSIZE - 1);
>
> Standard bit of code. I can't remember when I didn't know that one!

Yes, but I suppose the knowledge is fast eroding among coders. I can't
remember having been taught it. I must have learned it from other
people's assembly and C code.

Somehow that reminds me of an ancient trick I learned from some TI-56
program. Here's a compact way to figure out how many days are between
any (ISO 8601) dates:

========================================================================
#!/usr/bin/env python

import sys

def gregorian_day_count(isodate):
    year, month, day = map(int, isodate.split('-'))
    a, b = divmod(12 * year + month + 1185, 12)
    return int(a * 365.2425) + int(30.573 * b + 0.706) + day

def main():
    print gregorian_day_count(sys.argv[2]) - gregorian_day_count(sys.argv[1])

if __name__ == '__main__':
    main()
========================================================================

Usage:

    ./datediff.py 1960-02-03 2014-09-09


Marko

[toc] | [prev] | [next] | [standalone]

#5010

On Sun, 21 Sep 2014 00:48:44 +0300, Marko Rauhamaa wrote:

> Bob Eager <news0002@eager.cx>:
> 
>>>    (mqhp->mq_maxsz + MQ_ALIGNSIZE - 1) & ~(MQ_ALIGNSIZE - 1);
>>
>> Standard bit of code. I can't remember when I didn't know that one!
> 
> Yes, but I suppose the knowledge is fast eroding among coders. I can't
> remember having been taught it. I must have learned it from other
> people's assembly and C code.
> 
> Somehow that reminds me of an ancient trick I learned from some TI-56
> program. Here's a compact way to figure out how many days are between
> any (ISO 8601) dates:
> 
> ========================================================================
> #!/usr/bin/env python
> 
> import sys
> 
> def gregorian_day_count(isodate):
>     year, month, day = map(int, isodate.split('-'))
>     a, b = divmod(12 * year + month + 1185, 12)
>     return int(a * 365.2425) + int(30.573 * b + 0.706) + day
> 
> def main():
>     print gregorian_day_count(sys.argv[2]) -
>     gregorian_day_count(sys.argv[1])
> 
> if __name__ == '__main__':
>     main()
> ========================================================================
> 
> Usage:
> 
>     ./datediff.py 1960-02-03 2014-09-09
> 
> 
> Marko

Didn't know that one...thanks!



-- 
Using UNIX since v6 (1975)...

Use the BIG mirror service in the UK:
 http://www.mirrorservice.org

[toc] | [prev] | [next] | [standalone]

#5011

Bob Eager <news0002@eager.cx>:

> On Sun, 21 Sep 2014 00:48:44 +0300, Marko Rauhamaa wrote:
>> def gregorian_day_count(isodate):
>>     year, month, day = map(int, isodate.split('-'))
>>     a, b = divmod(12 * year + month + 1185, 12)
>>     return int(a * 365.2425) + int(30.573 * b + 0.706) + day
>
> [...]
>
> Didn't know that one...thanks!

Except, you shouldn't believe everything you read on the Internet :) --
the above code had a bug which I noticed when I actually tested it.

Here's a correction:

   def gregorian_day_count(isodate):
       year, month, day = map(int, isodate.split('-'))
       a, b = divmod(12 * year + month - 3, 12)
       yeardays = a * 365 + a // 4 - a // 100 + a // 400
       return yeardays + int(30.573 * b + 0.706) + day

If you intend to use the code, you're well advised to test it yourself.


Marko

[toc] | [prev] | [next] | [standalone]

#5050

Marko Rauhamaa <marko@pacujo.net>:

>    def gregorian_day_count(isodate):
>        year, month, day = map(int, isodate.split('-'))
>        a, b = divmod(12 * year + month - 3, 12)
>        yeardays = a * 365 + a // 4 - a // 100 + a // 400
>        return yeardays + int(30.573 * b + 0.706) + day

Or, if you will:

    def gregorian_day_count(isodate):
        year, month, day = map(int, isodate.split('-'))
        a, b = divmod(12 * year + month - 3, 12)
        return (a * 365 + (a >> 2) - (a * 1311 >> 17) + (a * 1311 >> 19) +
                + (31306 * b + 722 >> 10))


Marko

[toc] | [prev] | [next] | [standalone]

#5053

Marko Rauhamaa <marko@pacujo.net> writes:

> Bob Eager <news0002@eager.cx>:
>
>> On Sun, 21 Sep 2014 00:48:44 +0300, Marko Rauhamaa wrote:
>>> def gregorian_day_count(isodate):
>>>     year, month, day = map(int, isodate.split('-'))
>>>     a, b = divmod(12 * year + month + 1185, 12)
>>>     return int(a * 365.2425) + int(30.573 * b + 0.706) + day
>>
>> [...]
>>
>> Didn't know that one...thanks!
>
> Except, you shouldn't believe everything you read on the Internet :) --
> the above code had a bug which I noticed when I actually tested it.
>
> Here's a correction:
>
>    def gregorian_day_count(isodate):
>        year, month, day = map(int, isodate.split('-'))
>        a, b = divmod(12 * year + month - 3, 12)
>        yeardays = a * 365 + a // 4 - a // 100 + a // 400
>        return yeardays + int(30.573 * b + 0.706) + day
>
> If you intend to use the code, you're well advised to test it yourself.

I found this one, which is similar in spirit but doesn't depend on
floats:

http://alcor.concordia.ca/~gpkatch/gdate-algorithm.html

function g(y,m,d)
  m = (m + 9) % 12
  y = y - m/10
  return 365*y + y/4 - y/100 + y/400 + (m*306 + 5)/10 + ( d - 1 )

-- 
Christian Neukirchen  <chneukirchen@gmail.com>  http://chneukirchen.org

[toc] | [prev] | [next] | [standalone]

#5020

On 20/09/2014 22:48, Marko Rauhamaa wrote:

> Yes, but I suppose the knowledge is fast eroding among coders

It's fast eroding in coders but not in *programmers*.

There is a difference.

[toc] | [prev] | [next] | [standalone]

#5009

On 21/09/2014 6:41 AM, Rich wrote:
> http://zinascii.com/2014/the-8-byte-two-step.html
>
>     While studying the Illumos queue implementation I came across a line of
>     code that left me quite perplexed.
>
>     #define MQ_ALIGNSIZE 8 /* 64-bit alignment */ ... temp = (mqhp->mq_maxsz
>     + MQ_ALIGNSIZE - 1) & ~(MQ_ALIGNSIZE - 1);
>
>     I knew it had something to do with alignment on a 64-bit boundary, but
>     just how the hell was it doing it? Why is it subtracting one from the
>     alignment size? Why is it negating the expression on the right? Why is
>     it adding to the max message size? What the hell is going on?
>
>     At first I attempted to derive the pattern in my head but kept losing my
>     place; forced to start over multiple times. After placing my pride on
>     the bookshelf next to me, I wrote some C to help decode the mystery. The
>     program breaks the expression into its three parts, printing the base-2
>     representation of each step. Here are some test runs with different
>     sizes:
>
>     ...
>

The thinking behind the caculation is just this: Add an amount that is 
guaranteed to take you to or beyond the next multiple of the alignment 
size, and then throw away the remainder by subtracting the result modulo 
the alignment size. In this case, since the alignment size is a power of 
two, the latter step can be achieved using a mask rather than the much 
more expensive division.

Sylvia

[toc] | [prev] | [standalone]

Back to top | Article view | comp.misc

csiph-web