flat assembler
Message board for the users of flat assembler.

Index > IDE Development > Wink 6.92.03 (vertical selection + compiling)

Goto page Previous  1, 2, 3 ... 10, 11, 12 ... 19, 20, 21  Next
Author
Thread Post new topic Reply to topic
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
baldr wrote:
Collisions are inevitable. You can design hash function carefully to minimize them, though: mnemonics are composed from limited alphabet, up to six-digit base-36 number fits into 32 bits.

In fact hashes are often used as a first stage of exact matching algorithms. Consider file comparison to find duplicates: first compare hashes (CRC-32, for example), when they match, compare files bytewise.
The method for gaining good speed is to use small hash (like 16-bit one) and make a lookup table for all of this hash values, each one point to the list of only the items that have that hash. Thus even though the collisions are inevitable, you gain speed because looking up hash in the hash table may be just one MOV instruction, and after that you only have to search the items that collided.

Of course if you can still minimize the collisions, you can get even better speed gain. fasm's parser uses binary tree of 32-bit FNV-1a hashes when looking up label, for example.
Post 11 Sep 2010, 07:01
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
baldr wrote:
ouadji,
Collisions are inevitable, in fact hashes are often used as a first stage of exact matching algorithms.
Here is the key of the problem! Hashes are not used to find the solution,
but only to reduce the number of possibilities before the exact matching algorithms.

My current solution is a alphabetical classification.
Not a complete alphabetical classification ... only groups of words that start with the same letter.
This allows me to put the most used words in the beginning of each group.

The hashes_code takes time.
A first search is necessary (hash_code)... then a second search (exact matching algorithms) ...
I'm not sure that the time saved will be significant.
what do you think about this ?

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 10:26
View user's profile Send private message Send e-mail Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17475
Location: In your JS exploiting you and your system
revolution
ouadji wrote:
I'm not sure that the time saved will be significant.
what do you think about this ?
Code up both solutions and test it. One of three things will happen:
  1. A is faster than B, so use A
  2. B is faster than A, so use B
  3. The difference is not detectable, so use whatever was easier to code and debug
Post 11 Sep 2010, 10:30
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
Quote:

1. A is faster than B, so use A
2. B is faster than A, so use B
3. The difference is not detectable, so use whatever was easier to code and debug

fantastic algorythm !
thank you Revolution, you're a mother to me!
(i'm teasing you)

Wink

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 10:39
View user's profile Send private message Send e-mail Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
Code:
;...
;jb  hash_label
;--------------------------> right after your FNV-1a
       mov     ebp,eax
     shl     eax,8
       and     ebp,0FFh shl 24
     xor     ebp,eax
     or      ebp,ebx
;--------------------------<
;mov      [label_hash],ebp
;...
    

Why this Tomasz ? thank you.

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 11:46
View user's profile Send private message Send e-mail Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Oh, yeah, I forgot about this little quirk. The FNV-1a is xor-folded down to 24 bits and the remaining 8 bits of 32-bit value are used to store the length of symbol. This way collisions occur only for the symbols of the same length, so it simplifies comparisons a bit.
Post 11 Sep 2010, 12:16
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji

understood ! (good idea)

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 13:39
View user's profile Send private message Send e-mail Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji

1750 keywords : FNV-1A 32bits algorythm finds no Collision.

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 20:30
View user's profile Send private message Send e-mail Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
As you can see hashing method is quite good. The main problem is to find the proper hash function. Wink
Post 11 Sep 2010, 20:40
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji

yes, but ... (i don't understand)
no collison, ok ... (inside my hash table)
but i can find in the file a word that gives the same digital signature as a keyword included in my hash table
... while this word is not a keyword.

???

edit:
I think I understand ... to each hash code = a keyword ...(if no collision)
Even if two codes match,
I'm also forced to check the two strings .

Confused

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 20:53
View user's profile Send private message Send e-mail Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
ouadji wrote:

yes, but ... (i don't understand)
no collison, ok ... (inside my hash table)
but i can find in the file a word that gives the same digital signature as a keyword included in my hash table
... while this word is not a keyword.

???
Confused
Firstly, you can check the length of the token and compare it with the maximum length of the keywords stored in your table. If the token length is bigger you will know that it's a "false positive".

Secondly, if your token has the same hash as some of the keywords you can start to compare those strings in order to determine whether it's a "false positive" or not.

Thirdly, I guess that if you calculate hash with another one method the probability that you'll get a "false positive" will be close to 0 (so, maybe it would be good to have two tables of hashes calculated using two different hashing methods).
Post 11 Sep 2010, 21:12
View user's profile Send private message Visit poster's website Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji
Quote:

it would be good to have two tables of hashes calculated using two different hashing methods
ok, understood MHajduk (thank you)
very good idea


edit:
i feel that "Wink" is going to put his foot down ! Wink

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 11 Sep 2010, 21:16
View user's profile Send private message Send e-mail Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2941
Location: vpcmipstrm
bitRAKE
To simplify color theme changes here is a tool to use the many existing themes for Visual Studio. Wink Please include this with WINK if you wish. Should be easy to adapt to future WINK changes. (Also useful for FASMW.)

It only updates the [Colors] section of Wink INI file using Visual Studio settings file.

Known Problems:
- default color tag (0x02000000) not handled correctly (wip)


Description: Update0: removed debug line left in error
Update1: several more bug fixes

Download
Filename: vss2wink.asm
Filesize: 4.65 KB
Downloaded: 76 Time(s)


_________________
¯\(°_o)/¯ unlicense.org
Post 12 Sep 2010, 03:06
View user's profile Send private message Visit poster's website Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
Image
Post 13 Sep 2010, 11:56
View user's profile Send private message Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji

please, send me the file that caused the problem.
Have you been able to reproduce this problem?

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 13 Sep 2010, 16:51
View user's profile Send private message Send e-mail Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
i was editing code below, it won't compile



Code:
format pe gui 4.0
include 'win32ax.inc'

section '' code executable import readable writeable
  library kernel32,'kernel32.dll',\
          user32,'user32.dll'

  include 'api\kernel32.inc'
  include 'api\user32.inc'







  include '../macro.inc'
;  include '../proc.inc'

  bsa src,'0.1'

  entry $

        stdcall bsa_a2f,src,0+"'"
        ret     0





proc bsa_a2f; src, options
        stc
        pushf
        enter   12 +4 +1+255+4,0

        push    esi
        xor     esi,esi
        or      esi,[ebp+3*4]
        jz      .pepsi
        movzx   eax,byte[esi-4]
        shl     eax,8
        jz      .pepsi

        lea     edi,[ebp+4]
        mov     byte[ebp],0

        cld
.load:  lodsb
        cmp     al,'-'
        je      .sign
        cmp     al,'+'
        je      .sign
        cmp     al,'.'
        je      .dot
        cmp     al,','
        je      .dot
        cmp     al,'e'
        je      .exp
        cmp     al,'E'
        je      .exp
        sub     al,'0'
        cmp     al,9
        ja      .done
        stosb
        inc     byte[ebp]
.sign:
.dot:
.exp:

.pepsi: pop     esi
        leave
        popf
        ret     2*4
endp




; integer     -> ebx:eax
; result.79   -> flags.cf
; flags.cf    <- 1 if zero
; ecx:ebx:eax <- tbyte float
;
; example:
;   or      eax,-1
;   or      ebx,-1
;   clc
;   call    i2f    ; ecx:ebx:eax = $3fff+63'ffffffff'ffffffff = +18'446'744'073'709'551'615
;   or      eax,-1
;   or      ebx,-1
;   stc
;   call    i2f    ; ecx:ebx:eax = $bfff+63'ffffffff'ffffffff = -18'446'744'073'709'551'615
proc i2f
        pushf
        xor     ecx,ecx
        cmp     ebx,ecx
        jnz     .hnz
        cmp     eax,ecx
        jnz     .lnz
        bts     dword[esp],0
        jmp     .sign
.lnz:   xchg    ebx,eax
        sub     ecx,32
.hnz:   push    edx
        bsr     edx,ebx
        neg     edx
        add     edx,31
        neg     edx
        lea     ecx,[$3fff+63+ecx+edx]
        neg     edx
        xchg    cl,dl
        shld    ebx,eax,cl
        shl     eax,cl
        mov     cl,dl
        pop     edx
        shl     ecx,1
        btr     dword[esp],0
.sign:  rcr     cx,1
        popf
        ret     0
endp




; normalized mantissa -> ebx:eax
; ebx:eax             <- if fp_div: normalized (mantissa * 0.1)
;                        if fp_mul: normalized (mantissa * 10.0)
; ecx                 <- exponent delta
; flags               <- ?
proc fp_div
        push    edx
        mov     edx,$cccc'cccc
        mov     ecx,$cccc'cccd
        call    _64mul64        ; 0.1 = $3ffb'cccccccc'cccccccd, exp = -4
        mov     eax,ecx
        bsr     ecx,edx
        neg     ecx
        add     ecx,31
        shld    edx,eax,cl
        shld    eax,ebx,cl
        mov     ebx,edx
        pop     edx
        neg     ecx
        sub     ecx,3           ; -63*2 -4 +64 +64 -1 =-3
        ret     0
endp
; fasm internals simulator
proc fp_mul
        push    edx
        mov     edx,$a000'0000
        xor     ecx,ecx
        call    _64mul64        ; 10.0 = $4002'a0000000'00000000, exp = +3
        mov     eax,ecx
        bsr     ecx,edx
        neg     ecx
        add     ecx,31
        shld    edx,eax,cl
        shld    eax,ebx,cl
        mov     ebx,edx
        pop     edx
        neg     ecx
        add     ecx,4           ; -63*2 +3 +64 +64 -1 =4
        ret     0
endp




; edx:ecx:ebx:eax <- edx:ecx * ebx:eax = (edx*ebx:eax) shl 32 + ecx*ebx:eax
; flags           <- result.edx + 0
;
; $ffffffff'ffffffff * $ffffffff'ffffffff = $ffffffff'ffffffff * $1'00000000'00000000 - $ffffffff'ffffffff = $ffffffff'ffffffff'00000000'00000000 - $ffffffff'ffffffff = $ffffffff'fffffffe'00000000'00000001 = 128bit
proc _64mul64
        push    ecx ebx eax
        mov     ecx,edx
        call    _64mul32
        xchg    ecx,[esp+8]
        xchg    ebx,[esp+4]
        xchg    eax,[esp]
        call    _64mul32
        pop     edx
        add     ebx,edx
        pop     edx
        adc     ecx,edx
        pop     edx
        adc     edx,0
        ret     0
endp




; ecx:ebx:eax <- ecx * ebx:eax = (ecx*ebx) shl 32 + ecx*eax
; edx         <- ecx*eax
; flags       <- result.ecx + 0
;
; $ffffffff'ffffffff * $ffffffff = $ffffffff'ffffffff * $1'00000000 - $ffffffff'ffffffff = $ffffffff'ffffffff'00000000 - $ffffffff'ffffffff = $fffffffe'ffffffff'00000001 = 96bit
proc _64mul32
      xchg    ebx,eax
      mul     ecx
      xchg    ebx,eax
      xchg    edx,ecx
      mul     edx
      add     ebx,edx
      adc     ecx,0
      ret     0
endp
    


macro.inc
Code:
; pushrl 3,2,1 -> push 1 2 3
macro pushrl [values*]{reverse push values}




; gets defined if used in source only
; bsw name,'s1','s2' -> Borland String Wide
;   jmp @f
;   name#.size = @f-name-2
;   dd -1,name#.size
;   name du 's1','s2',0x00
;   @@:
macro bsw name*, [data]{
common
  if(used name)|(used name#.size)
    common
      jmp @f
      dd -1,?
      label name
    forward
      if ~data eq
        du data
      end if
    common
      name#.size = $-name
      store dword name#.size at name-4
      dw 0
      @@:
  end if
}





; gets defined if used in source only
; bsw s1,'s1'
; bsw s2,'s2'
; bsw2 name,s1,s1 ->
;   jmp @f
;   name.size = @f-2-name
;   dd -1,name.size
; label name
;   name.s1 dd s1
;   name.s2 dd s2
;   dw 0
;   @@:
macro bsw2 name*,[data]{
common
  if(used name)|(used name#.size)
    common
      jmp @f
      dd -1,?
      label name
    forward
      if(~data eq)
        name#.#data dd data
      end if
    common
      name#.size = $-name
      store dword name#.size at name-4
      dw 0
      @@:
  end if
}




; val   = 0..2^64-1
; merge = 0<bytes<9 of value to show
; example: repeat 8
;            display 13,10
;            ShowHex $FEDCBA9876543210,%
;          end repeat
macro ShowHex val*, merge*{
  if merge > 0 & merge < 9
    local .a, .merge
    .merge = (merge) shl 1
    while .merge <> 0
      .a = (val) shr ((.merge - 1) * 4) and 1111b or 11'0000b
      if .a > 11'1001b
        .a = .a + 111b
      end if
      display .a
      .merge = .merge - 1
    end while
  end if
}




;tf f1,$3fff-0000,$8000000000000000 ;2^0*1
;tf f2,$bfff-0064,$8000000000000000 ;2^-64*1
macro tf name*, exponent*, significand*{
  label name tbyte at $
  dq significand
  dw exponent
}




;display 13,10,'dd 0.1: '
;ShowFloat dd 0.1
;
;display 13,10,'dq 0.1: '
;ShowFloat dq 0.1
;
;display 13,10,'dt 0.1: '
;ShowFloat dt 0.1
;
;display 13,10,'3.1416: '
;ShowFloat dt 3.14159265358979323
macro ShowFloat command*{
  local .a
  virtual at 0
    command
    if $=4
      load .a dword from 0
      ShowHex .a,4
    else if $=8
      load .a qword from 0
      ShowHex .a,8
    else if $=10
      load .a word from 8
      ShowHex .a,2
      display "'"
      load .a qword from 0
      ShowHex .a,8
    end if
  end virtual
}




;display 13,10,13,10,'not colored, 4 bytes per address, no byte dump, yes ansi dump, width=1'
;dump _START,_END-_START,0,4,0,1,1
;display 13,10,13,10,'colored, 4 bytes per address, yes byte dump, no ansi dump, width=2'
;dump _START,_END-_START,1,4,1,0,2
;display 13,10,13,10,'colored, 8 bytes per address, yes byte dump, yes ansi dump, width=3'
;dump _START,_END-_START,1,8,1,1,3
;display 13,10,13,10,'not colored, 0 bytes per address, yes byte dump, no ansi dump, width=16'
;dump _START,_END-_START,0,0,1,0,16
;display 13,10,13,10,'not colored, 0 bytes per address, no byte dump, yes ansi dump, width=64'
;dump _START,_END-_START,0,0,0,1,64
;display 13,10,13,10,'not colored, 0 bytes per address, no byte dump, no ansi dump, width=0'
;dump _START,_END-_START,0,0,0,0,0
macro dump start*, count*, funky_colored?*, address*, show_dump?, show_text?*, width*{
  ;whether the weather is good ?
  if count<>0 & (address<>0 | show_dump?<>0 | show_text?<>0) & width<>0
     local .offset,.a
     .offset = 0
     ;dumper submacro
     macro dump _count\{
       if _count<>0
         ;new line
         display 13,10
         ;funky_colored?
         if funky_colored?<>0
           if .offset and 10000b = 0
             display "'"
           else
             display ';'
           end if
         end if
         ;address
         ShowHex start+.offset,address
         ;show_dump?
         if show_dump?<>0
           display ';'
           repeat _count
             display ' '
             load .a byte from start+.offset
             .offset = .offset+1
             ShowHex .a,1
           end repeat
           times (width)*3-_count*3 display ' '
         end if
         ;show_text?
         if show_text?<>0
           display '; '
           if show_dump?<>0
             .offset = .offset-_count
           end if
           repeat _count
             load .a byte from start+.offset
             .offset = .offset+1
             if .a<32
               .a = '.'
             end if
             display .a
           end repeat
         end if
       end if
     \}
     ;whole lines
     repeat (count)/(width)
       dump width
     end repeat
     ;fractional line
     dump (count) mod (width)
     ;free submacro
     purge dump
  end if
}




;/*
;  bsa name,'s1','s2' -> Borland String ANSI
;  if used name | used name.size
;    name.size = 4
;    dd -1(constant),name.size
;    label name
;    db 's1','s2',0
;  end if
;*/
macro bsa name*, [data]{
common
  if used name | used name#.size
    common
      dd -1,?
      label name
    forward
      if ~data eq
        db data
      end if
    common
      name#.size = $-name
      store dword name#.size at name-4
      db 0
  end if
}
    
Post 13 Sep 2010, 18:35
View user's profile Send private message Reply with quote
ouadji



Joined: 24 Dec 2008
Posts: 1081
Location: Belgium
ouadji

thank you edemko for this feedback
I'm sorry for this inconvenience.
I will fix that.

_________________
I am not young enough to know everything (Oscar Wilde)- Image
Post 13 Sep 2010, 18:47
View user's profile Send private message Send e-mail Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
Have you found the solution?
Unlike times before, files being edited were unaltered.
Post 13 Sep 2010, 18:58
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
edemko wrote:
Code:
;tf f1,$3fff-0000,$8000000000000000 ;2^0*1
;tf f2,$bfff-0064,$8000000000000000 ;2^-64*1
macro tf name*, exponent*, significand*{
  label name tbyte at $
  dq significand
  dw exponent
}    
You can do it like this:
Code:
f1 dt $3fff-0000:$8000000000000000
f2 dt $bfff-0064:$8000000000000000    
No need for a macro here.
Post 13 Sep 2010, 18:58
View user's profile Send private message Visit poster's website Reply with quote
edemko



Joined: 18 Jul 2009
Posts: 549
edemko
Tomasz killed me ...
Post 13 Sep 2010, 19:20
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3 ... 10, 11, 12 ... 19, 20, 21  Next

< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.