{
$Id: set.inc,v 1.17 2003/12/24 22:38:24 peter Exp $
This file is part of the Free Pascal run time library.
Copyright (c) 1999-2000 by the Free Pascal development team
Include file with set operations called by the compiler
See the file COPYING.FPC, included in this distribution,
for details about the copyright.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
**********************************************************************}
{$define FPC_SYSTEM_HAS_FPC_SET_LOAD_SMALL}
function fpc_set_load_small(l: fpc_small_set): fpc_normal_set;assembler;[public,alias:'FPC_SET_LOAD_SMALL']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
load a normal set p from a smallset l
}
var
saveedi : longint;
asm
movl %edi,saveedi
movl __RESULT,%edi
movl l,%eax
stosl
xorl %eax,%eax
movl $7,%ecx
rep
stosl
movl saveedi,%edi
end;
{$define FPC_SYSTEM_HAS_FPC_SET_CREATE_ELEMENT}
function fpc_set_create_element(b : byte): fpc_normal_set;assembler;[public,alias:'FPC_SET_CREATE_ELEMENT']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
create a new set in p from an element b
}
var
saveedi : longint;
asm
{$ifndef hascompilerproc}
pushl %eax
pushl %ecx
{$endif not hascompilerproc}
movl %edi,saveedi
movl __RESULT,%edi
movzbl b,%edx
xorl %eax,%eax
movl $8,%ecx
rep
stosl
leal -32(%edi),%eax
btsl %edx,(%eax)
movl saveedi,%edi
{$ifndef hascompilerproc}
popl %ecx
popl %eax
{$endif hascompilerproc}
end;
{$define FPC_SYSTEM_HAS_FPC_SET_SET_BYTE}
{$ifdef hascompilerproc}
function fpc_set_set_byte(const source: fpc_normal_set; b : byte): fpc_normal_set;assembler; compilerproc;
{
add the element b to the set pointed by source
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl source,%esi
movl __RESULT,%edi
movzbl b,%edx
movl $8,%ecx
rep
movsl
leal -32(%edi),%eax
btsl %edx,(%eax)
movl saveedi,%edi
movl saveesi,%esi
end;
{$else hascompilerproc}
function fpc_set_set_byte(b : byte): fpc_normal_set;assembler;[public,alias:'FPC_SET_SET_BYTE'];
{
add the element b to the set pointed by p
}
asm
pushl %eax
movl __RESULT,%edi
movb b,%al
andl $0xf8,%eax
shrl $3,%eax
addl %eax,%edi
movb b,%al
andl $7,%eax
btsl %eax,(%edi)
popl %eax
end;
{$endif hascompilerproc}
{$define FPC_SYSTEM_HAS_FPC_SET_UNSET_BYTE}
{$ifdef hascompilerproc}
function fpc_set_unset_byte(const source: fpc_normal_set; b : byte): fpc_normal_set;assembler; compilerproc;
{
add the element b to the set pointed by source
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl source,%esi
movl __RESULT,%edi
movzbl b,%edx
movl $8,%ecx
rep
movsl
leal -32(%edi),%eax
btrl %edx,(%eax)
movl saveedi,%edi
movl saveesi,%esi
end;
{$else hascompilerproc}
function fpc_set_unset_byte(b : byte): fpc_normal_set;assembler;[public,alias:'FPC_SET_UNSET_BYTE']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
suppresses the element b to the set pointed by p
used for exclude(set,element)
}
asm
pushl %eax
movl __RESULT,%edi
movb b,%al
andl $0xf8,%eax
shrl $3,%eax
addl %eax,%edi
movb b,%al
andl $7,%eax
btrl %eax,(%edi)
popl %eax
end;
{$endif hascompilerproc}
{$define FPC_SYSTEM_HAS_FPC_SET_SET_RANGE}
{$ifdef hascompilerproc}
function fpc_set_set_range(const orgset: fpc_normal_set; l,h : byte): fpc_normal_set;assembler; compilerproc;
{
adds the range [l..h] to the set pointed to by p
}
var
saveh : byte;
saveesi,saveedi,saveebx : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl %ebx,saveebx
movl __RESULT,%edi // target set address in edi
movl orgset, %esi // source set address in esi
movzbl l,%eax // lowest bit to be set in eax
movzbl h,%ebx // highest in ebx
movb %bl,saveh
movl $8,%ecx // we have to copy 32 bytes
cmpl %eax,%ebx // high < low?
rep // copy source to dest (it's possible to do the range
movsl // setting and copying simultanuously of course, but
// that would result in many more jumps and code)
movl %eax,%ecx // lowest also in ecx
jb .Lset_range_done // if high > low, then dest := source
shrl $3,%eax // divide by 8 to get starting and ending byte
shrl $3,%ebx // address
andb $31,%cl // low five bits of lo determine start of bit mask
andl $0x0fffffffc,%eax // clear two lowest bits to get start/end longint
subl $32,%edi // get back to start of dest
andl $0x0fffffffc,%ebx // address * 4
movl $0x0ffffffff,%edx // edx = bitmask to be inserted
shll %cl,%edx // shift bitmask to clear bits below lo
addl %eax,%edi // go to starting pos in set
subl %eax,%ebx // are bit lo and hi in the same longint?
jz .Lset_range_hi // yes, keep current mask and adjust for hi bit
orl %edx,(%edi) // no, store current mask
movl $0x0ffffffff,%edx // new mask
addl $4,%edi // next longint of set
subl $4,%ebx // bit hi in this longint?
jz .Lset_range_hi // yes, keep full mask and adjust for hi bit
.Lset_range_loop:
movl %edx,(%edi) // no, fill longints in between with full mask
addl $4,%edi
subl $4,%ebx
jnz .Lset_range_loop
.Lset_range_hi:
movb saveh,%cl // this is ok, h is on the stack
movl %edx,%ebx // save current bitmask
andb $31,%cl
subb $31,%cl // cl := (31 - (hi and 31)) = shift count to
negb %cl // adjust bitmask for hi bit
shrl %cl,%edx // shift bitmask to clear bits higher than hi
andl %edx,%ebx // combine both bitmasks
orl %ebx,(%edi) // store to set
.Lset_range_done:
movl saveedi,%edi
movl saveesi,%esi
movl saveebx,%ebx
end;
{$else hascompilerproc}
function fpc_set_set_range(l,h : byte): fpc_normal_set;assembler;[public,alias:'FPC_SET_SET_RANGE'];
{
adds the range [l..h] to the set pointed to by p
}
asm
movl __RESULT,%edi // set address in edi
movzbl l,%eax // lowest bit to be set in eax
movzbl h,%ebx // highest in ebx
cmpl %eax,%ebx
jb .Lset_range_done
movl %eax,%ecx // lowest also in ecx
shrl $3,%eax // divide by 8 to get starting and ending byte
shrl $3,%ebx // address
andb $31,%cl // low five bits of lo determine start of bit mask
movl $0x0ffffffff,%edx // edx = bitmask to be inserted
andl $0x0fffffffc,%eax // clear two lowest bits to get start/end longint
andl $0x0fffffffc,%ebx // address * 4
shll %cl,%edx // shift bitmask to clear bits below lo
addl %eax,%edi // go to starting pos in set
subl %eax,%ebx // are bit lo and hi in the same longint?
jz .Lset_range_hi // yes, keep current mask and adjust for hi bit
orl %edx,(%edi) // no, store current mask
movl $0x0ffffffff,%edx // new mask
addl $4,%edi // next longint of set
subl $4,%ebx // bit hi in this longint?
jz .Lset_range_hi // yes, keep full mask and adjust for hi bit
.Lset_range_loop:
movl %edx,(%edi) // no, fill longints in between with full mask
addl $4,%edi
subl $4,%ebx
jnz .Lset_range_loop
.Lset_range_hi:
movb h,%cl
movl %edx,%ebx // save current bitmask
andb $31,%cl
subb $31,%cl // cl := (31 - (hi and 31)) = shift count to
negb %cl // adjust bitmask for hi bit
shrl %cl,%edx // shift bitmask to clear bits higher than hi
andl %edx,%ebx // combine both bitmasks
orl %ebx,(%edi) // store to set
.Lset_range_done:
end;
{$endif hascompilerproc}
{$define FPC_SYSTEM_HAS_FPC_SET_IN_BYTE}
function fpc_set_in_byte(const p: fpc_normal_set; b: byte): boolean; assembler; [public,alias:'FPC_SET_IN_BYTE']; {$ifdef hascompilerproc} compilerproc; {$else} saveregisters; {$endif}
{
tests if the element b is in the set p the carryflag is set if it present
}
asm
{$ifdef hascompilerproc}
{$ifdef REGCALL}
xchgl %edx,%eax
andl $0xff,%eax
{$else}
movl p,%edx
movzbl b,%eax
{$endif}
btl %eax,(%edx)
{$else hascompilerproc}
pushl %eax
movl p,%edi
movzbl b,%eax
btl %eax,(%edi)
popl %eax
{$endif hascompilerproc}
end;
{$define FPC_SYSTEM_HAS_FPC_SET_ADD_SETS}
{$ifdef hascompilerproc}
function fpc_set_add_sets(const set1,set2: fpc_normal_set): fpc_normal_set;assembler;[public,alias:'FPC_SET_ADD_SETS']; compilerproc;
{$else hascompilerproc}
procedure fpc_set_add_sets(set1,set2,dest : pointer);assembler;[public,alias:'FPC_SET_ADD_SETS'];
{$endif hascompilerproc}
{
adds set1 and set2 into set dest
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
{$ifdef REGCALL}
movl set1,%esi
movl __RESULT,%edi
movl set2,%edx
{$else}
movl set1,%esi
movl set2,%edx
{$ifdef hascompilerproc}
movl __RESULT,%edi
{$else hascompilerproc}
movl dest,%edi
{$endif hascompilerproc}
{$endif}
movl $8,%ecx
.LMADDSETS1:
lodsl
orl (%edx),%eax
stosl
addl $4,%edx
decl %ecx
jnz .LMADDSETS1
movl saveedi,%edi
movl saveesi,%esi
end;
{$define FPC_SYSTEM_HAS_FPC_SET_MUL_SETS}
{$ifdef hascompilerproc}
function fpc_set_mul_sets(const set1,set2: fpc_normal_set): fpc_normal_set;assembler;[public,alias:'FPC_SET_MUL_SETS']; compilerproc;
{$else hascompilerproc}
procedure fpc_set_mul_sets(set1,set2,dest:pointer);assembler;[public,alias:'FPC_SET_MUL_SETS'];
{$endif hascompilerproc}
{
multiplies (takes common elements of) set1 and set2 result put in dest
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
{$ifdef REGCALL}
movl set1,%esi
movl __RESULT,%edi
movl set2,%edx
{$else}
movl set1,%esi
movl set2,%edx
{$ifdef hascompilerproc}
movl __RESULT,%edi
{$else hascompilerproc}
movl dest,%edi
{$endif hascompilerproc}
{$endif}
movl $8,%ecx
.LMMULSETS1:
lodsl
andl (%edx),%eax
stosl
addl $4,%edx
decl %ecx
jnz .LMMULSETS1
movl saveedi,%edi
movl saveesi,%esi
end;
{$define FPC_SYSTEM_HAS_FPC_SET_SUB_SETS}
{$ifdef hascompilerproc}
function fpc_set_sub_sets(const set1,set2: fpc_normal_set): fpc_normal_set;assembler;[public,alias:'FPC_SET_SUB_SETS']; compilerproc;
{$else hascompilerproc}
procedure fpc_set_sub_sets(set1,set2,dest:pointer);assembler;[public,alias:'FPC_SET_SUB_SETS'];
{$endif hascompilerproc}
{
computes the diff from set1 to set2 result in dest
}
var
saveesi,saveedi,saveebx : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl %ebx,saveebx
{$ifdef REGCALL}
movl set1,%esi
movl __RESULT,%edi
movl set2,%ebx
{$else}
movl set1,%esi
movl set2,%ebx
{$ifdef hascompilerproc}
movl __RESULT,%edi
{$else hascompilerproc}
movl dest,%edi
{$endif hascompilerproc}
{$endif}
movl $8,%ecx
.LMSUBSETS1:
lodsl
movl (%ebx),%edx
notl %edx
andl %edx,%eax
stosl
addl $4,%ebx
decl %ecx
jnz .LMSUBSETS1
movl saveedi,%edi
movl saveesi,%esi
movl saveebx,%ebx
end;
{$define FPC_SYSTEM_HAS_FPC_SET_SYMDIF_SETS}
{$ifdef hascompilerproc}
function fpc_set_symdif_sets(const set1,set2: fpc_normal_set): fpc_normal_set;assembler;[public,alias:'FPC_SET_SYMDIF_SETS']; compilerproc;
{$else hascompilerproc}
procedure fpc_set_symdif_sets(set1,set2,dest:pointer);assembler;[public,alias:'FPC_SET_SYMDIF_SETS'];
{$endif hascompilerproc}
{
computes the symetric diff from set1 to set2 result in dest
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
{$ifdef REGCALL}
movl set1,%esi
movl __RESULT,%edi
movl set2,%edx
{$else}
movl set1,%esi
movl set2,%edx
{$ifdef hascompilerproc}
movl __RESULT,%edi
{$else hascompilerproc}
movl dest,%edi
{$endif hascompilerproc}
{$endif}
movl $8,%ecx
.LMSYMDIFSETS1:
lodsl
xorl (%edx),%eax
stosl
addl $4,%edx
decl %ecx
jnz .LMSYMDIFSETS1
movl saveedi,%edi
movl saveesi,%esi
end;
{$define FPC_SYSTEM_HAS_FPC_SET_COMP_SETS}
function fpc_set_comp_sets(const set1,set2: fpc_normal_set): boolean;assembler;[public,alias:'FPC_SET_COMP_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
compares set1 and set2 zeroflag is set if they are equal
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl set1,%esi
movl set2,%edi
movl $8,%ecx
.LMCOMPSETS1:
movl (%esi),%eax
movl (%edi),%edx
cmpl %edx,%eax
jne .LMCOMPSETEND
addl $4,%esi
addl $4,%edi
decl %ecx
jnz .LMCOMPSETS1
{ we are here only if the two sets are equal
we have zero flag set, and that what is expected }
.LMCOMPSETEND:
{$ifdef hascompilerproc}
seteb %al
{$endif hascompilerproc}
movl saveedi,%edi
movl saveesi,%esi
end;
{$define FPC_SYSTEM_HAS_FPC_SET_CONTAINS_SET}
function fpc_set_contains_sets(const set1,set2: fpc_normal_set): boolean;assembler;[public,alias:'FPC_SET_CONTAINS_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
on exit, zero flag is set if set1 <= set2 (set2 contains set1)
}
var
saveesi,saveedi : longint;
asm
movl %edi,saveedi
movl %esi,saveesi
movl set1,%esi
movl set2,%edi
movl $8,%ecx
.LMCONTAINSSETS1:
movl (%esi),%eax
movl (%edi),%edx
andl %eax,%edx
cmpl %edx,%eax {set1 and set2 = set1?}
jne .LMCONTAINSSETEND
addl $4,%esi
addl $4,%edi
decl %ecx
jnz .LMCONTAINSSETS1
{ we are here only if set2 contains set1
we have zero flag set, and that what is expected }
.LMCONTAINSSETEND:
{$ifdef hascompilerproc}
seteb %al
{$endif hascompilerproc}
movl saveedi,%edi
movl saveesi,%esi
end;
{$ifdef LARGESETS}
{$error Needs to be fixed for register calling first!}
procedure fpc_largeset_set_word(p : pointer;b : word);assembler;[public,alias:'FPC_LARGESET_SET_WORD']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
sets the element b in set p works for sets larger than 256 elements
not yet use by the compiler so
}
asm
pushl %eax
movl p,%edi
movw b,%ax
andl $0xfff8,%eax
shrl $3,%eax
addl %eax,%edi
movb 12(%ebp),%al
andl $7,%eax
btsl %eax,(%edi)
popl %eax
end;
procedure fpc_largeset_in_word(p : pointer;b : word);assembler;[public,alias:'FPC_LARGESET_IN_WORD']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
tests if the element b is in the set p the carryflag is set if it present
works for sets larger than 256 elements
}
asm
pushl %eax
movl p,%edi
movw b,%ax
andl $0xfff8,%eax
shrl $3,%eax
addl %eax,%edi
movb 12(%ebp),%al
andl $7,%eax
btl %eax,(%edi)
popl %eax
end;
procedure fpc_largeset_add_sets(set1,set2,dest : pointer;size : longint);assembler;[public,alias:'FPC_LARGESET_ADD_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
adds set1 and set2 into set dest size is the number of bytes in the set
}
asm
movl set1,%esi
movl set2,%ebx
movl dest,%edi
movl size,%ecx
.LMADDSETSIZES1:
lodsl
orl (%ebx),%eax
stosl
addl $4,%ebx
decl %ecx
jnz .LMADDSETSIZES1
end;
procedure fpc_largeset_mul_sets(set1,set2,dest : pointer;size : longint);assembler;[public,alias:'FPC_LARGESET_MUL_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
multiplies (i.E. takes common elements of) set1 and set2 result put in
dest size is the number of bytes in the set
}
asm
movl set1,%esi
movl set2,%ebx
movl dest,%edi
movl size,%ecx
.LMMULSETSIZES1:
lodsl
andl (%ebx),%eax
stosl
addl $4,%ebx
decl %ecx
jnz .LMMULSETSIZES1
end;
procedure fpc_largeset_sub_sets(set1,set2,dest : pointer;size : longint);assembler;[public,alias:'FPC_LARGESET_SUB_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
asm
movl set1,%esi
movl set2,%ebx
movl dest,%edi
movl size,%ecx
.LMSUBSETSIZES1:
lodsl
movl (%ebx),%edx
notl %edx
andl %edx,%eax
stosl
addl $4,%ebx
decl %ecx
jnz .LMSUBSETSIZES1
end;
procedure fpc_largeset_symdif_sets(set1,set2,dest : pointer;size : longint);assembler;[public,alias:'FPC_LARGESET_SYMDIF_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
computes the symetric diff from set1 to set2 result in dest
}
asm
movl set1,%esi
movl set2,%ebx
movl dest,%edi
movl size,%ecx
.LMSYMDIFSETSIZE1:
lodsl
movl (%ebx),%edx
xorl %edx,%eax
stosl
addl $4,%ebx
decl %ecx
jnz .LMSYMDIFSETSIZE1
end;
procedure fpc_largeset_comp_sets(set1,set2 : pointer;size : longint);assembler;[public,alias:'FPC_LARGESET_COMP_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
asm
movl set1,%esi
movl set2,%edi
movl size,%ecx
.LMCOMPSETSIZES1:
lodsl
movl (%edi),%edx
cmpl %edx,%eax
jne .LMCOMPSETSIZEEND
addl $4,%edi
decl %ecx
jnz .LMCOMPSETSIZES1
{ we are here only if the two sets are equal
we have zero flag set, and that what is expected }
.LMCOMPSETSIZEEND:
end;
procedure fpc_largeset_contains_sets(set1,set2 : pointer; size: longint);assembler;[public,alias:'FPC_LARGESET_CONTAINS_SETS']; {$ifdef hascompilerproc} compilerproc; {$endif}
{
on exit, zero flag is set if set1 <= set2 (set2 contains set1)
}
asm
movl set1,%esi
movl set2,%edi
movl size,%ecx
.LMCONTAINSSETS2:
movl (%esi),%eax
movl (%edi),%edx
andl %eax,%edx
cmpl %edx,%eax {set1 and set2 = set1?}
jne .LMCONTAINSSETEND2
addl $4,%esi
addl $4,%edi
decl %ecx
jnz .LMCONTAINSSETS2
{ we are here only if set2 contains set1
we have zero flag set, and that what is expected }
.LMCONTAINSSETEND2:
end;
{$endif LARGESET}
{
$Log: set.inc,v $
Revision 1.17 2003/12/24 22:38:24 peter
* fix set_set_range
Revision 1.16 2003/12/04 21:42:07 peter
* register calling updates
Revision 1.15 2003/12/03 23:06:35 peter
* more fixes
Revision 1.14 2003/12/03 22:46:54 peter
* typo in sub_set
Revision 1.13 2003/11/23 16:50:49 peter
* register calling updates
Revision 1.12 2003/11/11 21:08:17 peter
* REGCALL define added
Revision 1.11 2003/09/08 18:21:37 peter
* save edi,esi,ebx
Revision 1.10 2003/05/26 19:36:46 peter
* fpc_shortstr_concat is now the same for all targets
* fpc_shortstr_append_shortstr added for optimized code generation
Revision 1.9 2002/09/07 16:01:19 peter
* old logs removed and tabs fixed
Revision 1.8 2002/03/29 20:15:44 peter
* fixed load_smallset
}
syntax highlighted by Code2HTML, v. 0.9.1