[fasmg] Lucas Prime Test

Index > Macroinstructions > [fasmg] Lucas Prime Test

Goto page Previous 1, 2, 3

Author

Thread

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8349
Location: Kraków, Poland

Tomasz Grysztar 14 Sep 2020, 19:49

bitRAKE wrote:

Maybe a useful perspective?

Code:

previous value:

        N/A             discarded       preserved       brought back    /w transfer

        :=              =               =:              restore
                        reequ           equ             restore
                        redefine        define          restore
        macro:                          macro           purge           mvmacro
                                        struc           restruc         mvstruc

In the last column for expression-class symbols you could perhaps put "[CALM] take".

14 Sep 2020, 19:49

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 14 Sep 2020, 20:37

The term "symbol" has always tripped me up. "=-+!%" are symbols, but named variables are "identifiers". This is a personal problem of navigating the abstractions as all identifiers are symbols.

Thanks for the addition - CALM hasn't been integrated into my thinking about fasmg. I've converted a couple macro/struc, but not enough.

14 Sep 2020, 20:37

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 29 May 2021, 03:11

Code:

; Create static bit vector:
; + ignore value set duplicates
; + invert value set when bit length is negative
struc(name) BITVECTOR bits,values&
        local result,offset,char,inverted,_bits
        virtual
                offset = $
                db values ; string or byte array
                result = 0
                while offset < $
                        load char:1 from offset
                        offset = offset + 1
                        result = result or (1 shl char)
                end while
        end virtual
        if bits < 0
                _bits = -bits
                inverted = (1 shl _bits) - 1
        else
                _bits = bits
                inverted = 0
        end if
        if result shr _bits
                err 'value exceeds bit vector size'
        end if
        name: emit (_bits + 7) shr 3 : (result xor inverted)
end struc

align 32
InvalidFileNameChars BITVECTOR -256,"!#$%&'()-@^_`{}~+,.;=[]0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


FileNameValid__RSI:
        xor eax,eax
.more:
        lodsb
        test eax,eax ; CF=0
        jz .done
        bt [InvalidFileNameChars],eax
        jnc .more
.done:
        retn
; CF: file name has invalid characters


FileNameValid__RSI__ECX: ; ECX > 0
.more:
        dec ecx ; requres previous CF result on exit
        js .done
        movzx eax,byte[rsi+rcx]
        bt [InvalidFileNameChars],eax
        jnc .more
.done:
        retn
; CF: file name has invalid characters


macro ValidateFileName reg0,reg1
        local more,done
more:   dec reg32.#reg1 ; requres previous CF result on exit
        js done
        movzx eax,byte[reg0+reg1]
        bt [InvalidFileNameChars],eax
        jnc more
done:
end macro

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

29 May 2021, 03:11

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 19 Jun 2021, 21:57

another example of using BITVECTOR macro:

whitespace detection, 32 bytes of data, smallest number of comparisons, don't modify character:

Code:

align 32
WSA0:   BITVECTOR 20 shl 3,0x09,0x0A,0x0B,0x0C,0x0D,0x20
WS2000: BITVECTOR 12 shl 3,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x28,0x29,0x2F,0x5F

; fast path the byte-like whitespace
UTF32_Whitespace:
        cmp eax,0xA0 ; U+00A0 non-breaking space
        jnc .high
        bt [WSA0],eax ; [00-9F] ; 20 bytes
        retn
.high:
        jz .space
        cmp eax,0x2000
        jc .notspace
        cmp eax,0x2060
        jnc .cjk
        bt [WS2000 - (0x2000 shr 3)],eax ; [2000-205F] ; 12 bytes
        retn
.space:
        stc
        retn
.cjk:
;       jz .space
        cmp eax,0x3000
        jz .space
.notspace:
        clc
        retn

(Note: inverting the return flag would save a couple bytes of code.)

The above method has more control, imho (spaces are not all equal in terms of use). Binary search used 52 bytes, but less code. Something like:

Code:

        mov offset,1
        jmp @F0
@1:     adc offset,offset
        cmp offset,sizeof list
        jc @F2 ; not found, ZF=0
@0:     cmp word [list + offset*2 - 2],item
        jnz @B1
@2:

...could use a larger tree and priority sort to bias search - more cache misses, more comparisons.

Edit: is there a faster way - yes, always, yes. How about a perfect hash? We can imagine some function like:

Code:

imul ecx,eax,CONST0
and ecx,CONST1 ; or probable shr ecx,CONST1
bt [bvCONST],ecx

...just need to solve for CONST0 whilst minimizing the size of the bit vector (CONST1) for our set of characters. Maybe, there isn't a solution and then we increase the complexity. We can even imagine such a function might exist which doesn't need the bit vector. Producing the result in constant time. No one would be faulted for thinking that impossible.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

19 Jun 2021, 21:57

Goto page Previous 1, 2, 3

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum