Page 1 of 4 123 ... LastLast
Results 1 to 10 of 35

Thread: Nearest Power of 2 quickly

  1. #1

    Nearest Power of 2 quickly

    For my Tile Splicer I need a routine to calculate the nearest power of 2 for the output image. I know that the following code will work just fine, but it seems that their really should be a faster way (btw: I know that a shift is better then a *, but the optimizer takes care of it in this case).

    [pascal] if frmGenerate.SizePower2 then
    begin
    p2 := 2;
    while p2 < imgOut.Width do
    p2 := p2 * 2;
    imgOut.Width := p2;
    p2 := 2;
    while p2 < imgOut.Height do
    p2 := p2 * 2;
    imgOut.Height := p2;
    end;[/pascal]

    I know this is a simple, stupid question, but I've been stuck for a bit trying to find a better way

  2. #2
    Co-Founder / PGD Elder WILL's Avatar
    Join Date
    Apr 2003
    Location
    Canada
    Posts
    6,107
    Blog Entries
    25

    Nearest Power of 2 quickly

    Have you tried using a pre-calculated table?

    You can make it start at 2 and run up to whatever the highest size would be then you'd simply only have to run through the array until you find a size that fits.
    Jason McMillen
    Pascal Game Development
    Co-Founder





  3. #3

    Re: Nearest Power of 2 quickly

    This is a typical situation where some assembler can be usefull. Of course, always {$ifdef} the assembler code and put a Pascal version in the {$else} part to not hurt portabilty.

    [pascal]
    if frmGenerate.SizePower2 then
    begin
    w:=imgout.width;
    h:=imgout.height;
    asm
    mov ebx,w
    bsr ecx,ebx
    mov ebx,1
    inc ecx
    shl ebx,ecx
    mov w,ebx

    mov ebx,h
    bsr ecx,ebx
    mov ebx,1
    inc ecx
    shl ebx,ecx
    mov h,ebx
    end;
    end;
    [/pascal]

  4. #4

    Nearest Power of 2 quickly

    Here's an alternative code I've been distributing in Asphyre package:

    Code:
    function NextPowerOfTwo&#40;Value&#58; Integer&#41;&#58; Integer;
    begin
     Result&#58;= 1;
     asm
      xor ecx, ecx
      bsr ecx, Value
      inc ecx
      shl Result, cl
     end;
    end;
    Code:
    function CeilPowerOfTwo&#40;Value&#58; Integer&#41;&#58; Integer;
    asm
     mov ecx, eax
     xor eax, eax
     dec ecx
     bsr ecx, ecx
     cmovz ecx, eax
     setnz al
     inc eax
     shl eax, cl
    end;

  5. #5

    Nearest Power of 2 quickly

    OH for crying out loud Here are two no-assembly, portable algorythms i use, first one i came up with, it's based on idea of second algorythm, which is from wikipedia (or the other way round).

    Code:
    if &#40;number and &#40;number - 1&#41; <> 0&#41; // FAST POT CHECK
    
    trunc&#40;power&#40;2, trunc&#40;Log2&#40;number&#41;&#41;&#41;&#41;; // MAKE NUMBER A POT, ROUND UP
    This is my game project - Top Down City:
    http://www.pascalgamedevelopment.com...y-Topic-Reboot

    My OpenAL audio wrapper with Intelligent Source Manager to use unlimited:
    http://www.pascalgamedevelopment.com...source+manager

  6. #6

    Nearest Power of 2 quickly

    :shock: :shock: Do you have any idea how slow a trunc is?

    No, for speed you need to do it with integer logic. This is a way how you can do it in Pascal:

    dec(v);
    v:=v or (v shr 1) or (v shr 2) or (v shr 4) or (v shr 8 ) or (v shr 16);
    inc(v);

    ... but even this one is slower than the assembler one. The ancient art proves itself usefull once more!

  7. #7

    Nearest Power of 2 quickly

    Quote Originally Posted by dmantione
    :shock: :shock: Do you have any idea how slow a trunc is?
    why would trunc be slow? it executes on the FPU, right?
    This is my game project - Top Down City:
    http://www.pascalgamedevelopment.com...y-Topic-Reboot

    My OpenAL audio wrapper with Intelligent Source Manager to use unlimited:
    http://www.pascalgamedevelopment.com...source+manager

  8. #8

    Nearest Power of 2 quickly

    Quote Originally Posted by Delfi
    Quote Originally Posted by dmantione
    :shock: :shock: Do you have any idea how slow a trunc is?
    why would trunc be slow? it executes on the FPU, right?
    This is the trunc implementation in FPC

    [pascal]
    {$define FPC_SYSTEM_HAS_TRUNC}
    function fpc_trunc_real(d : ValReal) : int64;assembler;compilerproc;
    var
    oldcw,
    newcw : word;
    res : int64;
    asm
    fnstcw oldcw
    fwait
    movw oldcw,%cx
    orw $0x0f00,%cx
    movw %cx,newcw
    fldcw newcw
    fldt d
    fistpq res
    fwait
    movl res,%eax
    movl res+4,%edx
    fldcw oldcw
    end;
    [/pascal]

    Note all the hackery with the FPU control word, necessary to make the FPU truncate instead of round. Tinkering with the fpucw is terribly expensive.

  9. #9

    Nearest Power of 2 quickly

    Never mind.
    [size=10px]&quot;In science one tries to tell people, in such a way as to be understood by everyone, something that no one ever knew before. But in poetry, it&#39;s the exact opposite.&quot; -- Paul Dirac[/size]

  10. #10

    Nearest Power of 2 quickly

    I cant think of any situation where a power of 2 calculation is not fast enough...

    You normally use this when loading textures in which case the disk access is going to slow it down no matter what. I know jdarling didnt ask for the fastest thing out there, but it's a classic example of the 90% - 10% optimisation mantra:

    90% of the code you write will be executed once or twice
    the other 10% will be executed very many more times (thousands of times per second?)

    And to optimize code that falls into the first 90% is a waste of time. You need to figure out if this code really falls into that last 10% before you start worrying that the trunc() procedure is not fast enough

    Just for luck, this is how I implemented it.. using the suggested lookup-table.

    Code:
    const
       Pow2&#58; array&#91;0..12&#93; of integer = &#40;2,4,8,16,32,64,128,256,512,1024,2048,4096,8192&#41;;
    
    Function GetNextPow2&#40;Wid&#58; integer&#41;&#58; integer;
    var I&#58; integer;
    begin
      Result &#58;= Wid;
    
      for I &#58;= 1 to 12 do
      begin
       If Pow2&#91;I&#93; >= Wid then
       begin
         Result &#58;= Pow2&#91;I-1&#93;;
         exit;
       end;
      end;
    
    
    end;
    
    Function GetPrevPow2&#40;Wid&#58; integer&#41;&#58; integer;
    var I&#58; integer;
    begin
      Result &#58;= Wid;
    
      for I &#58;= 12 downto 1 do
      begin
       If Pow2&#91;I&#93; <= Wid then
       begin
         Result &#58;= Pow2&#91;I-1&#93;;
         exit;
       end;
      end;
    
    
    end;
    My site: DelphiTuts.com (coming soon)...

    Download Font Studio 4.21 here.

Page 1 of 4 123 ... LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •