unit integer_maths;

{$MODE OBJFPC}

interface
uses type_fixes;

function INTLOG2(aValue : TUINT32) : TUINT16;
function CountBits(aValue : TUINT32) : TUINT16; overload;

implementation

// by Dann Corbit:
function INTLOG2(aValue : TUINT32) : TUINT16;
begin
  { TODO check aValue = 0 => exception. }

  Result := 0;
  if (aValue and $FFFF0000) <> 0 then
    Result := 16;

  aValue := aValue shr Result;
  if (aValue and $FF00) <> 0 then begin
    Result := Result or 8;
    aValue := aValue shr 8;
  end;

  if (aValue and $F0) <> 0 then begin
    Result := Result or 4;
    aValue := aValue shr 4;
  end;

  if (aValue and $C) <> 0 then begin
    Result := Result or 2;
    aValue := aValue shr 2;
  end;

  Result := TUINT16(Result or (aValue shr 1));
end;

{ see Software Optimization Guide for AMD Athlon 64 and Opteron Processors. }
function CountBits(aValue : TUINT32) : TUINT16; overload;
begin
  aValue := aValue - ((aValue shr 1) and $55555555); // reuse input as temp.
  aValue := (aValue and $33333333) + ((aValue shr 2) and $33333333); // temp.
  Result := (((aValue + (aValue shr 4)) and $F0F0F0F) * $1010101) shr 24;

  { in a generic way:
      v = v - ((v >> 1) & (T)~(T)0/3); / temp.
      v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp.
      v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp.
      c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT;
  }
end;

end.