Computing Padding Algorithm

[prazetto]

For some obvious reason,

Sucessfully to translate an #computing padding algorithm,

and outputting same value with example of an explanation

Lets take a breath, wiki say:

The following formulas provide the number of padding bytes required to align the start of a data structure (where mod is the modulo operator):

# pseudo-code, see actual code below
padding = (align - (offset mod align)) mod align
new offset = offset + padding = offset + (align - (offset mod align)) mod align

For example, the padding to add to offset 0x59d for a structure aligned to every 4 bytes is 3. The structure will then start at 0x5a0, which is a multiple of 4. Note that when offset already is a multiple of align, the second modulo in (align - (offset mod align)) mod align is required to get a padding of 0.

Then I write AutoIt3 script.

ConsoleWrite(@CR & '+ Computing padding' & @CR)
Local $align, $offset, $padding, $new_offset

$align = 4
$offset = 0x59d

$padding = Mod($align - Mod($offset, $align), $align)
$new_offset = $offset + $padding + Mod($offset + ($align - Mod($offset, $align)), $align)

ConsoleWrite('padding: ' & $padding & '  new offset: 0x' & StringLower(Hex($new_offset, 4)) & @CR)

And the output is match with example in explanation.

+ Computing padding
padding: 3  new offset: 0x05a0

The question #01 are is that are correct translation? changing second line on second (=) (see below) with plus sign (+) in AutoIt3 (see above) ?

new offset = offset + padding = offset + (align - (offset mod align)) mod align

.

Again lets take a breath, wiki say:

If the alignment is a power of two, the modulo operation can be reduced to a bitwise boolean AND operation. The following formulas provide the new offset (where & is a bitwise AND and ~ a bitwise NOT):

padding = align - (offset & (align - 1)) = (-offset) & (align - 1)
new offset = (offset + align - 1) & ~(align - 1)

Then I write AutoIt3 script.

ConsoleWrite(@CR & '+ align 2 - Power of Two' & @CR)
Local $align, $offset, $padding, $new_offset

$align = 2
$offset = 0x59d

$padding = $align - (BitAND($offset, ($align - 1))) + BitAND((-$offset), ($align - 1))
$new_offset = BitAND(($offset + $align - 1), BitNOT($align - 1))

ConsoleWrite('padding: ' & $padding & '  new offset: 0x' & StringLower(Hex($new_offset, 4)) & @CR)

And the output is.

+ align 2 - Power of Two
padding: 2  new offset: 0x059e

The question #02. First line and second (=) I replace with plus (+) sign, again is that correct?

The question #03.

What is meaning from the word of 'The Power of Two'?

Are 2 is The Power of Two?

Are 4, 8, 16 is The Power of Two?

Which are the number are is The Power of Two and which is not?

Can someone give me an confirmation if translation that pseudo-code to AutoIt3 are correct.?

Can someone give me an explanation what is so called 'The Power of Two'.?

Please answer even if you think this are childish question, because I'm not from Brittain nor from American.

Edited March 15, 2014 by prazetto

[jchd]

You could be interessed in browsing this old thread, at least the posts about alignment and padding, roughly >starting here and on the following page.

The k^th power of number N is N multiplied k times by itself, which we write N^k. By convention and because it's true, N⁰ = 1.

Then N¹ = N, N² = N * N, N³ = N * N * N and so on.

Successive powers of 2 are: 1, 2, 4, 8, 16, 32, 64, ...

[prazetto]

@jchd

Thanks for the answer about the power of n and 2.

The link you pointed out are very helpfull for me.

Even the title of post are 'Latest Beta', but yes this are what I seek.

Now I can continue my project.

New update:

After reading those page back to 21, page 22 (pointed one) and next page 23.

At least it seem for me are temporary understand.

After try to understand then I try to translate and test.

The output size are match with DllStruct... family. Yes.

Finally:

expandcollapse popup

; assume member size
Local $size[] = [2, 2, 4, 8, 1, 2]

; assume align 8, start at offset 0
Local $nAlign = 8, _ ; value are align option : 1, 2, 4, 8, 16
      $iOffset = 0, _
      $nTemp = 0, _
      $nLargestSize = 8 ; there max(size[]) = 8

For $loop = 0 To UBound($size)-1
   $iDataTypeSize = $size[$loop]

   ; Does this offset need padding first for correct alignment?
   If $iDataTypeSize < $nAlign Then
      $nTemp = Mod($iOffset, $iDataTypeSize)
      If $nTemp Then $nTemp = $iDataTypeSize - $nTemp
      Else
      $nTemp = Mod($iOffset, $nAlign)
      If $nTemp Then $nTemp = $nAlign - $nTemp
      EndIf
      $iOffset += $nTemp ; Update offset with padding

   ConsoleWrite('offset: #' & $loop & '  @  0x' & Ptr($iOffset) & '  size: ' & $size[$loop] & @CR)
   $iOffset += $iDataTypeSize
Next

ConsoleWrite('offset: fn  @  0x' & Ptr($iOffset) & '  @pad :' & $iOffset & @CR)

   If ($nLargestSize < $nAlign) Then
      $nTemp = Mod($iOffset, $nLargestSize)
      If ($nTemp) Then $nTemp = $nLargestSize - $nTemp
      Else
      $nTemp = Mod($iOffset, $nAlign)
        If ($nTemp) Then $nTemp = $nAlign - $nTemp
      EndIf
    $iOffset = $iOffset + $nTemp;              // Update offset with padding

ConsoleWrite('offset: fn  @  0x' & Ptr($iOffset) & '  fin. :' & $iOffset & @CR & @CR)


ConsoleWrite('Compare with Native function' & @CR)
Local $mystruct = DllStructCreate('align ' & $nAlign & '; word; word; dword; int64; byte; word;')
ConsoleWrite('DllStruct* Family : ' & DllStructGetSize($mystruct) & @CR)

For $loop = 1 To 6
   ConsoleWrite('offset: #' & $loop-1 & '  @  ' & DllStructGetPtr($mystruct, $loop) - DllStructGetPtr($mystruct, 1) & @CR )
   Next

; jon:
;~ Individual member padding:
;~    // Does this offset need padding first for correct alignment?
;~    if (iDataTypeSize < nAlign)
;~    {
;~       nTemp = iOffset % iDataTypeSize;
;~       if(nTemp)
;~       nTemp = iDataTypeSize - nTemp;
;~    }
;~    else
;~    {
;~       nTemp = iOffset % nAlign;
;~       if(nTemp)
;~           nTemp = nAlign - nTemp;
;~    }
;~    iOffset += nTemp;                   // Update offset with padding

;~ End of structure padding:
;~    // Ensure the end of the structure is padded based on the size of the largest member
;~    if (nLargestSize < nAlign)
;~    {
;~       nTemp = iOffset % nLargestSize;
;~       if(nTemp)
;~           nTemp = nLargestSize - nTemp;
;~    }
;~    else
;~    {
;~       nTemp = iOffset % nAlign;
;~       if(nTemp)
;~           nTemp = nAlign - nTemp;
;~    }
;~    iOffset = iOffset + nTemp;              // Update offset with padding

; jchd:
;~ Individual member:
;~    // Does this offset need padding first for correct alignment of next member whose size is iDataTypeSize?
;~    nTemp = min(iDataTypeSize, nAlign);
;~    iOffset += (nTemp - (iOffset % nTemp)) % nTemp;                 // Update offset with padding

;~ Struct tail:
;~    // Ensure the end of the structure is padded based on the size of the smallest of (largest member or pack size)
;~    nTemp = min(nLargestSize, nAlign);
;~    iOffsetIn = iOffset + (nTemp - (iOffset % nTemp)) % nTemp;      // Update offset with padding

Output:

offset: #0  @  0x0x00000000  size: 2
offset: #1  @  0x0x00000002  size: 2
offset: #2  @  0x0x00000004  size: 4
offset: #3  @  0x0x00000008  size: 8
offset: #4  @  0x0x00000010  size: 1
offset: #5  @  0x0x00000012  size: 2
offset: fn  @  0x0x00000014  @pad :20
offset: fn  @  0x0x00000018  fin. :24

Compare with Native function
DllStruct* Family : 24
offset: #0  @  0x00000000
offset: #1  @  0x00000002
offset: #2  @  0x00000004
offset: #3  @  0x00000008
offset: #4  @  0x00000010
offset: #5  @  0x00000012

See the twenty four number!

Try change $nAlign, in my test. All align option 1, 2, 4, 8, 16 are match with native DllStruct... family.

Edited March 17, 2014 by prazetto