[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]

{
Just for fun, I sat down last night and generated an inline asm version
of the C code I posted that permuted character strings.  This version
uses about 90 clock cycles/call on a 486 and 60 on a Pentium, i.e.
one microsecond/call on my P5-60:  (The average time is very nearly
independent of the length of the string.)

From: terjem@hda.hydro.com (Terje Mathisen)
}

{$R-,S-}
Program Permutate;

Function Permute(var a; alen : word): Boolean;
Assembler;
asm
  push ds         { BX -> beginning of array }
  lds bx,[a]
  mov di,[alen]   { Array length }
  xor cx,cx       { Return value = False }
  lea si,[di+bx-2]{ SI -> one character before last }
  lea di,[di+bx-1]{ DI -> last position in a[] }

@loop1:
  cmp si,bx       { Check if we've gotten to the beginning of the array!}
   jb @reverse    { Yes, so no permutation found, return reversed array!}
  mov ax,[si]     { Get another pair of bytes from the end }
  dec si
  cmp al,ah
   jae @loop1     { Loop until a[si] < a[si+1] }

{ We have found a pair of bytes where the first is less than
  the second, which means that there exists at least one more
  permutation of the a[] array.
}

  mov bx,di       { BX -> Last byte in a[] }
  inc si          { SI was decremented one extra time, adjust back }
  mov cl,True     { Return value = True }

{ Find the last byte which is > al (a[si]) }

@loop2:
  mov dl,[bx]
  dec bx
  cmp dl,al
   jbe @loop2

{ Swap the two positions found: }

  mov [si],dl
  mov [bx+1],al
   jmp @reverse   { Reverse the rest of the array! }

@loop3:
  mov al,[si]
  mov dl,[di]
  mov [di],al
  dec di
  mov [si],dl
@reverse:
  inc si
  cmp si,di
   jb @loop3

  mov ax,cx
  pop ds
end;

var
  test, org : String;
  n : LongInt;

begin
  org := ParamStr(1);
  test := org;
  n := 0;

  if ParamCount > 1 then begin {Verbose version }
    repeat
      WriteLn(n:10,' ',test);
      Inc(n);
    until not Permute(test[1],Length(test));
    WriteLn(n:10,' ',test);
  end
  else begin
    repeat
      Inc(n);
    until not Permute(test[1],Length(test));
    WriteLn(n,' permutations of ',org,' found!');
  end;
end.

[Back to MATH SWAG index]  [Back to Main SWAG index]  [Original]