Swapping an array

General FreeBASIC programming questions.
RockTheSchock
Posts: 228
Joined: Mar 12, 2006 16:25

Swapping an array

Postby RockTheSchock » Nov 16, 2007 14:25

I want to swap an array

wether array1 = array2 nor swap(array1,array2) are working
i don't want to copy the arrays, I only want to swap the array descriptors

Code: Select all

ReDim newlist(1000) As String
ReDim filelist(1000) As String

Dim changed As String

getFiles("*.*",&h21, filelist() )

Do   
   getFiles("*.*",&h21, newlist() )
 
   changed = intersect(newlist(),filelist())
   If Len(changed)>0 Then      
      swap filelist,newlist 'or filelist = newlist
   EndIf
Loop Until InKey=Chr(27)

D.J.Peters
Posts: 8023
Joined: May 28, 2005 3:28
Contact:

Postby D.J.Peters » Nov 16, 2007 14:54

simple swap pointers on your array
(you can read a whole array from file to pointer and
you can write a whole array from pointer to file)

dim as datatype array_a(max_items)
dim as datatype array_b(max_items)
dim as datatype ptr lpArray_a=@array_a(0)
dim as datatype ptr lpArray_b=@array_b(0)

use your array's as before
array_a/b(index)=value
value=array_a/b(index)

or use it as pointer
lpArray_a/b[index]=value
value=lpArray_a/b[index]

if condition then swap lpArray_a,lpArray_b

get or put lpArray_a or _b from/to file
http://www.freebasic.net/wiki/wikka.php ... gGetfileio
http://www.freebasic.net/wiki/wikka.php ... gPutfileio

Joshy
Zippy
Posts: 1295
Joined: Feb 10, 2006 18:05

Postby Zippy » Nov 16, 2007 19:22

Yes you can (corrupt memory in a few clock cycles).

Note that this is probably safe enough (albeit I'm saying that after limited testing..) as long as you stay within the bounds of your dynamic variable length string arrays. This method exclusive to/for dynamic string arays.

Code: Select all

'swap dynamic variable length string array descriptors
'
redim newlist (1000) as string 'NOTE: dynamic!
redim filelist(1000) as string 'NOTE: dynamic!
'
dim as integer a,b,MAXS=25
dim as integer ptr nptr,fptr
'
'put something in arrays
for a=0 to MAXS
    newlist(a)=chr(a+65)
    filelist(a)=chr(a+97)
next
'
print "NEWLIST : ";
for a=0 to MAXS:?newlist(a);:next:?
'
print "FILELIST: ";
for a=0 to MAXS:?filelist(a);:next:?
'
for a= 0 to MAXS
    nptr=cast(integer ptr,@newlist(a))
    fptr=cast(integer ptr,@filelist(a))
    '
    for b=0 to 2
        swap *(fptr+b),*(nptr+b)
    next
next
'
print
print "NEWLIST : ";
for a=0 to MAXS:?newlist(a);:next:?
'
print "FILELIST: ";
for a=0 to MAXS:?filelist(a);:next:?
'
sleep
end

Note I've used (0) as lbound.

Chow,Z.

ETA: Seems to work with static arrays also, not certain why I thought it wouldn't..
stylin
Posts: 1253
Joined: Nov 06, 2005 5:19

Postby stylin » Nov 16, 2007 20:46

RockTheSchock, arrays currently cannot be wholly swapped like that, but you can hack a rather unsafe workaround:

A declaration for a swap proc that will accept any kind of array (a.bas):

Code: Select all

' a() and b() are assumed to have an equal number of dimensions.
declare sub Swap_ (a() as any, b() as any)

function ToString (array() as string) as string
   var result = ""
   for index as integer = lbound(array) to ubound(array)
      result &= "[" & array(index) & "]"
   next
   return result
end function

dim a(2) as string = { "one", "two", "three" }
dim b(2) as string = { "four", "five", "six" }

print "a: " & ToString(a())
print "b: " & ToString(b())

Swap_(a(), b())

print "a: " & ToString(a())
print "b: " & ToString(b())

Then, the definition takes references to array descriptors (b.bas):

Code: Select all

# include once "crt/string.bi" ' for memcpy

type FBArrayDimInfo
   as integer   elements, lbound, ubound
end type

type FBArrayDescriptor
   enum : MAX_DIMENSIONS = 8 : end enum
   
   as any ptr         data, p
   as integer         size, element_size, dimensions
end type

# define FBARRAY_DESC_SIZE(n) (sizeof(FBArrayDescriptor) + sizeof(FBArrayDimInfo) * (n))

sub Swap_ (byref a as FBArrayDescriptor, byref b as FBArrayDescriptor)
   static tmp(1 to FBARRAY_DESC_SIZE(FBArrayDescriptor.MAX_DIMENSIONS)) as ubyte
   
   var sz = FBARRAY_DESC_SIZE(a.dimensions)
   
   ..memcpy(@tmp(1), @b,      sz)
   ..memcpy(@b,      @a,      sz)
   ..memcpy(@a,      @tmp(1), sz)
end sub


Compile those files with fbc a.bas b.bas to see the results. Like D.J.Peters says, a much easier approach might be to reference the arrays with pointers and swap those.
RockTheSchock
Posts: 228
Joined: Mar 12, 2006 16:25

Macro swapping Arrays

Postby RockTheSchock » Nov 17, 2007 4:29

I am tired after 5 hours. I think it works without problems.
I know that calling memcopy is ugly but it's 5am. After sleeping i will code this little step. Perhaps there will be someone else finished first.

Code: Select all

#Include "crt.bi"

#Macro SwapArrays(arr,arr2)
Scope
#If ( TypeOf(arr)=TypeOf(arr2) )   
   Dim lpArr As Any Ptr
   Dim lpArr2 As Any Ptr
   Dim Arr3(32) As Byte
   
   Asm            
      lea eax,[a-32]         
      mov [lpArr],eax            
      lea eax,[b-32]      
      mov [lpArr2],eax         
   End Asm
      
         
   memcpy( @Arr3(0), lpArr,  32 )
   memcpy( lpArr, lpArr2, 32 )      
   memcpy( lpArr2, @Arr3(0), 32 )      
#EndIf
End Scope
#EndMacro


Screen 12

ReDim a(100,101) As FBArray
ReDim b(10,11) As FBArray

SwapArrays(a,b)
Print UBound(a,2),UBound(b,2)
sleep
RockTheSchock
Posts: 228
Joined: Mar 12, 2006 16:25

Better Version of swaparrays macro

Postby RockTheSchock » Nov 17, 2007 14:52

Code: Select all

#Macro SwapArrays(arr,arr2)
Scope
#If ( TypeOf(arr)=TypeOf(arr2) )   
   Asm
      lea eax,[a]   'the adress of the array descriptor begins
      lea ebx,[b]   'at [a-32]. Begin to swap at  the tail
                                   'of the array descriptor
                                
      mov ecx,8         '32 bytes 8 * dword   
   swaploop:                 'swap array descriptors   
      mov edx,[eax]      
      xchg [ebx],edx
      mov [eax],edx
      sub eax,4
      Sub ebx,4
      dec ecx
      jnz swaploop      
   End Asm
#EndIf
End Scope
#EndMacro
Zippy
Posts: 1295
Joined: Feb 10, 2006 18:05

Re: Better Version of swaparrays macro

Postby Zippy » Nov 17, 2007 19:10

RockTheSchock wrote:

Code: Select all

#Macro SwapArrays(arr,arr2)
Scope
#If ( TypeOf(arr)=TypeOf(arr2) )   
   Asm
      lea eax,[a]   'the adress of the array descriptor begins
      lea ebx,[b]   'at [a-32]. Begin to swap at  the tail
                                   'of the array descriptor
                                
      mov ecx,8         '32 bytes 8 * dword   
   swaploop:                 'swap array descriptors   
      mov edx,[eax]      
      xchg [ebx],edx
      mov [eax],edx
      sub eax,4
      Sub ebx,4
      dec ecx
      jnz swaploop      
   End Asm
#EndIf
End Scope
#EndMacro

I had to make one slight change in your asm to create a working example:

Code: Select all


#Macro SwapArrays(a,b)
Scope
#If ( TypeOf(a)=TypeOf(b) )
        Asm
                lea eax,[a]   'the adress of the array descriptor begins
                lea ebx,[b]   'at [a-32]. Begin to swap at  the tail
                                   'of the array descriptor
                                   
                'changed to 9                   
                mov ecx,9         '32 bytes 8 * dword
       
        swaploop:                 'swap array descriptors       
                mov edx,dword ptr [eax]               
                xchg dword ptr [ebx],edx
                mov dword ptr [eax],edx
                Sub eax,4
                Sub ebx,4
                dec ecx
                jnz swaploop               
        End Asm
        beep
#EndIf
End Scope
#EndMacro
'
redim newlist (0 to 99) as string
    newlist(0)=" NEW-ONE"
    newlist(1)=" NEW-TWO"
    newlist(2)=" NEW-THREE"
'
redim oldlist (0 to 99) as string
    oldlist(0)=" old-one"
    oldlist(1)=" old-two"
    oldlist(2)=" old-three"
'
dim as integer a
 '   
print "Before swap:":?
print "NEWLIST: ";
for a=0 to 2:?newlist(a);:next:?
'
print "OLDLIST: ";
for a=0 to 2:?oldlist(a);:next:?
'
SwapArrays(oldlist,newlist)
'
'
print
print "After swap:":?
print "NEWLIST: ";
for a=0 to 2:?newlist(a);:next:?
'
print "OLDLIST: ";
for a=0 to 2:?oldlist(a);:next:?
'
sleep
end

That's a nice solution, Rock.

I formalized my version. I'll post for gaggles. It'll handle mixed string array types (dynamic and not), disparate array dimensions (gotta mind those bounds yourself), and allow partial swaps:

Code: Select all

'swap string arrays (element descriptors)
'
dim newlist (1 to 99) as string
    newlist(1)=" NEW-ONE"
    newlist(2)=" NEW-TWO"
    newlist(3)=" NEW-THREE"
   
redim oldlist (1 to 99) as string
    oldlist(1)=" old-one"
    oldlist(2)=" old-two"
    oldlist(3)=" old-three"
'
dim as integer a
'
declare sub swap_strarrays(s1() as string,_
                           s2() as string,_
                           as integer,_
                           as integer)
'
print "Before swap:":?
print "NEWLIST: ";
for a=1 to 3:?newlist(a);:next:?
'
print "OLDLIST: ";
for a=1 to 3:?oldlist(a);:next:?
'
' (array one,array two,lbound,ubound)
swap_strarrays(oldlist(),newlist(),1,3)
'
'
print
print "After swap:":?
print "NEWLIST: ";
for a=1 to 3:?newlist(a);:next:?
'
print "OLDLIST: ";
for a=1 to 3:?oldlist(a);:next:?
'
sleep
end
'
sub swap_strarrays(s1() as string,_
                   s2() as string,_
                   MINS as integer,_
                   MAXS as integer)
'
    dim as integer a,b
    dim as integer ptr s1ptr,s2ptr
    '
    'error checking, my my
    MINS=iif(MINS<lbound(s1),lbound(s1),MINS)
    MINS=iif(MINS<lbound(s2),lbound(s2),MINS)
    MAXS=iif(MAXS>ubound(s1),ubound(s1),MAXS)
    MAXS=iif(MAXS>ubound(s2),ubound(s2),MAXS)   
    '
    for a= MINS to MAXS
        s1ptr=cast(integer ptr,@s1(a))
        s2ptr=cast(integer ptr,@s2(a))
        '
        for b=0 to 2
            swap *(s1ptr+b),*(s2ptr+b)
        next
    next
'
end sub

I may post an array copy function later. Maybe not.

@stylin

Thanks for the example using the descriptor passed to a sub. That's what cha0s was talking about. Wow.
notthecheatr
Posts: 1759
Joined: May 23, 2007 21:52
Location: Cut Bank, MT
Contact:

Postby notthecheatr » Nov 18, 2007 2:16

For integer arrays, of course, the fastest way to swap is to use Xor (RockTheShock's example would be faster than mine since I don't use assembly, but mine will be more readable - his uses Xchg, a processor command which AFAIK works the same way as mine):

Code: Select all

Dim As Integer a(10), b(10)
Dim As Integer i

'Initialize arrays so a(i) = i and b(i) = -i.
For i = 1 To 10
  a(i) = i
  b(i) = -i
Next i

'Display contents of arrays
For i = 1 To 10
  Print a(i)
  Print b(i)
Next i

'Sleep to allow it to be viewed
Sleep

'Then clear the screen
Cls

'Swap contents of the arrays using a special Xor trick
For i = 1 To 10
  a(i) Xor = b(i)
  b(i) Xor= a(i)
  a(i) Xor = b(i)
Next i

'Display the values of the arrays
For i = 1 To 10
  Print a(i)
  Print b(i)
Next i

'Sleep again to allow it to be viewed
Sleep


The triple-Xor trick is well-known to do this, the only non-benefit being that it doesn't exactly improve readability D:
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Postby MichaelW » Nov 18, 2007 9:11

It is a nice solution, but the asm code is far from optimum, so much so that I would not be surprised if a pure FB version were faster.

Code: Select all

'====================================================================
#include "windows.bi"
#include "counter.bas"
'====================================================================
'' Counter.bas is available here:
''
'' http://www.freebasic.net/forum/viewtopic.php?t=4221
'====================================================================

Redim newlist (0 To 99) As String
    newlist(0)=" NEW-ONE"
    newlist(1)=" NEW-TWO"
    newlist(2)=" NEW-THREE"

Redim oldlist (0 To 99) As String
    oldlist(0)=" old-one"
    oldlist(1)=" old-two"
    oldlist(2)=" old-three"

sleep 3000

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  asm
    lea eax,[oldlist-4]
    lea ebx,[newlist-4]
    mov ecx, 8
  L1:
    mov edx, [eax]
    xchg [ebx], edx
    mov [eax], edx
    sub eax, 4
    sub ebx, 4
    dec ecx
    jnz L1
  end asm
counter_end
print counter_cycles; " cycles"

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  asm
    lea eax,[oldlist-32]
    lea ebx,[newlist-32]
    mov ecx, 7
    push esi
  L2:
    mov edx, [eax+ecx*4]
    mov esi, [ebx+ecx*4]
    mov [ebx+ecx*4], edx
    mov [eax+ecx*4], esi
    dec ecx
    jns L2
    pop esi
  end asm
counter_end
print counter_cycles; " cycles"

sleep

Typical results on my P3:

Code: Select all

230 cycles
39 cycles

For a 7-instruction loop repeating 8 times, 230 cycles works out to about 4 cycles per instruction executed. Optimized integer code running on a recent processor should typically be more like 1 cycle per instruction executed.

BTW, the main problem with the code is the XCHG instruction. Per Agner Fog’s optimizing_assembly PDF, available here, the XCHG register,[memory] instruction “always has an implicit LOCK prefix which prevents it from using the cache”.

Also, I'm not sure that the constants I'm using are all correct, as I was just trying to get a representative cycle count.
Zippy
Posts: 1295
Joined: Feb 10, 2006 18:05

Postby Zippy » Nov 19, 2007 18:01

@MichaelW

Wow, a five-fold savings in cycles. Good information. xchg is OK for swapping register values?

=====

Given that for this method the strings must be dimensioned identically, only 2 dwords must be swapped:

Code: Select all

'swap string array descriptors
'
'...
asm
    lea eax,[oldlist-28]
    lea ebx,[newlist-28]
    mov ecx,[eax]
    mov edx,[ebx]
    mov [eax],edx
    mov [ebx],ecx
    sub eax,4
    sub ebx,4
    mov ecx,[eax]
    mov edx,[ebx]
    mov [eax],edx
    mov [ebx],ecx
end asm   
'...
'

It would be simpler if the stack address of the descriptor was accessible outside of asm. It isn't, varptr can't be used, thus RockTheShock's code was a great revelation to me (this simple mind).

This method of obtaining the stack address lends itself to resolution of another curiousity, that of how to point a numeric array to a memory buffer (in lieu of using pointers, etc.). Trivial:

Code: Select all

'numeric array, re-pointing to memory buffer
'
redim as integer n1(9)         'this only works with dynamic arrays,
                               'not shared, not static, not common
'
dim as string  s1=string(40,0) 'test buffer
dim as integer c
dim as integer ptr np
'
'fill test buffer
for c=0 to 39 step 4
    s1[c]=(c+1)\4
next
'
'get/put ptr numeric array descriptor    
asm
    mov ebx,[s1]  'strptr(s1) == memory buffer address
    lea eax,[n1]  'start address of numeric data, descriptor offset
    sub eax,24    'offset - 7th dword
    mov [eax],ebx
    sub eax,8     'offset - 8th dword
    mov [eax],ebx
end asm
'
'print numeric array
for c=0 to 9
    print "element:";c,"value:";n1(c)
next
'
sleep
end

A hack a day keeps..
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Postby MichaelW » Nov 19, 2007 19:12

I don’t generally use xchg for anything, so I had to test to be sure, and xchg reg,reg seems to be OK. I had to add the repeat directive because a lea combined with a single xchg reg.reg executed too fast to get a meaningful cycle count.

Code: Select all

'====================================================================
#include "windows.bi"
#include "counter.bas"
'====================================================================
'' Counter.bas is available here:
''
'' http://www.freebasic.net/forum/viewtopic.php?t=4221
'====================================================================

static as integer i

sleep 3000

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  asm
    lea eax, [i]
    .rept 10
      xchg [eax], edx
      xchg ecx, [eax]
    .endr
  end asm
counter_end
print counter_cycles

counter_begin( 1000, HIGH_PRIORITY_CLASS )
  asm
    lea eax, [i]
    .rept 10
      xchg eax, edx
      xchg ecx, eax
    .endr
  end asm
counter_end
print counter_cycles

sleep

Code: Select all

384
27

Return to “General”

Who is online

Users browsing this forum: No registered users and 6 guests