home *** CD-ROM | disk | FTP | other *** search
/ Fujiology Archive / fujiology_archive_v1_0.iso / !FALCON / MSB / QDSP014U.ZIP / QDSP014U / HASH.S < prev    next >
Text File  |  2013-12-19  |  10KB  |  515 lines
  1. ; hash table, self expanding, quadratic probing.
  2. ; can tell if label was found (for double labels errors and searching).
  3. ; meant for use in qdsp assembler.
  4.  
  5. Hash.ENTRIES:        =    1031    2053        ; nextprime(2048)
  6. Hash.BUFSIZE:        =    32768    65536
  7. Hash.DOUBLE_KEY:    =    -1
  8. Hash.REHASH_FAILED:    =    -2
  9. Hash.NULL_STRING:    =    -3
  10. Hash.REBUF_FAILED:    =    -4
  11.  
  12.     IFND    QDSP
  13.  
  14.     COMMENT    HEAD=%111
  15.  
  16.     bsr    Hash.init
  17.     tst.l    d0
  18.     bmi    exit    
  19.  
  20.     lea    Hash.string1,a0
  21.     moveq    #1,d1
  22.     bsr    addString0
  23.     tst.l    d0
  24.     bmi    deinit
  25.  
  26.     lea    Hash.string2,a0
  27.     moveq    #2,d1
  28.     bsr    addString0
  29.     tst.l    d0
  30.     bmi    deinit
  31.  
  32.     lea    Hash.string3,a0
  33.     moveq    #3,d1
  34.     bsr    addString0
  35.     tst.l    d0
  36.     bmi    deinit
  37.  
  38.     lea    Hash.string4,a0
  39.     moveq    #4,d1
  40.     bsr    addString0
  41.     tst.l    d0
  42.     bmi.s    deinit
  43.  
  44.     lea    Hash.string5,a0
  45.     moveq    #5,d1
  46.     bsr    addString0
  47.     tst.l    d0
  48.     bmi.s    deinit
  49.  
  50.     lea    Hash.string6,a0
  51.     moveq    #6,d1
  52.     bsr    addString0
  53.     tst.l    d0
  54.     bmi.s    deinit
  55.  
  56.     lea    Hash.string7,a0
  57.     moveq    #7,d1
  58.     bsr    addString0
  59.     tst.l    d0
  60.     bmi.s    deinit
  61.  
  62.     lea    Hash.string8,a0
  63.     moveq    #8,d1
  64.     bsr    addString0
  65.     tst.l    d0
  66.     bmi.s    deinit
  67.  
  68.     lea    Hash.string8,a0
  69.     moveq    #8,d1
  70.     bsr    addString0
  71.     tst.l    d0
  72.     bmi.s    deinit
  73.  
  74.     lea    Hash.string9,a0
  75.     moveq    #9,d1
  76.     bsr    addString0
  77.     tst.l    d0
  78.     bmi.s    deinit
  79.  
  80.     lea    Hash.string9,a0
  81.     move.w    len,d0
  82.     bsr    Hash.get
  83.     tst.w    Hash.wasFound
  84.     beq.s    deinit
  85.     
  86.     nop
  87.  
  88. deinit:    bsr    Hash.deinit
  89.  
  90. exit:    clr.w    -(sp)
  91.     trap    #1
  92.  
  93.     INCLUDE    INCLUDE\GEMDOS.S
  94.  
  95.     ENDC
  96.  
  97. ; INPUT:
  98. ; a0: string (null terminated)
  99. ; d1.l=data
  100. ; OUTPUT:
  101. ; d0.l= 0:ok, <0:error
  102. addString0:
  103.     movea.l    a0,a1
  104. .loop:    tst.b    (a1)+
  105.     bne.s    .loop
  106.     subq    #1,a1
  107.     sub.l    a0,a1
  108.     move.l    a1,d0
  109.     move.w    d0,len
  110.     bsr    Hash.add
  111.     rts
  112.  
  113. ; OUTPUT:
  114. ; d0.l= 0:ok, <0:error
  115. Hash.init:
  116.     move.l    #Hash.ENTRIES,d0
  117.     move.l    d0,Hash.numEntries
  118.     move.l    d0,d1
  119.     lsl.l    #2,d0                ; d0*4
  120.     Malloc    d0
  121.     move.l    d0,Hash.tableAdr
  122.     beq.s    .error
  123.  
  124. ; Clear hash table.
  125.     clr.l    Hash.numTaken            ; 0 occupied
  126.     movea.l    d0,a0                ; a0: table
  127.     clr.l    d0
  128. .loop:    move.l    d0,(a0)+
  129.     subq.l    #1,d1
  130.     bne.s    .loop
  131.  
  132. ; Allocate stringbuffer.
  133.     move.l    #Hash.BUFSIZE,d0
  134.     move.l    d0,Hash.bufSize
  135.     Malloc    d0
  136.     move.l    d0,Hash.bufferAdr
  137.     move.l    d0,Hash.nextStringAdr
  138.     beq.s    .error
  139.  
  140. ; Clear buffer.
  141.     movea.l    d0,a0                ; a0: buffer
  142.     move.l    Hash.bufSize,d1
  143.     clr.l    d0
  144. .cloop:    move.b    d0,(a0)+
  145.     subq.l    #1,d1
  146.     bne.s    .cloop
  147.  
  148.     moveq    #0,d0
  149.     rts
  150. .error:    moveq    #-1,d0
  151.     rts
  152.  
  153. ; PRE: Hash.init was successful
  154. Hash.deinit:
  155.     Mfree    Hash.bufferAdr
  156.     Mfree    Hash.tableAdr
  157.     rts
  158.  
  159. ; todo: check if entry already in here
  160. ; INPUT:
  161. ; a0: string
  162. ; d0.w=stringlength (0 gives error)
  163. ; d1.l=data
  164. ; OUTPUT:
  165. ; d0.l= 0:ok, <0:error
  166. Hash.add:
  167.     movem.l    d2-d7/a1-a6,-(sp)
  168.  
  169.     move.l    a0,a6
  170.     move.w    d0,.stringsize
  171. .redo:    bsr    Hash.calcKey            ; d0.l=key
  172.     tst.w    Hash.wasFound
  173.     bne.s    .success
  174.     tst.l    d0
  175.     bmi    .null_string
  176.  
  177. ; Insert the stingaddress in the table.
  178.     movea.l    Hash.tableAdr,a1
  179.     movea.l    Hash.nextStringAdr,a2
  180.     move.l    a2,(a1,d0.l*4)
  181.  
  182. ; Check if we should rehash..
  183.     move.l    Hash.numTaken,d0
  184.     addq.l    #1,d0
  185.     add.l    d0,d0
  186.     cmp.l    Hash.numEntries,d0
  187.     bhs.s    .rehash                ; Too high load? -> Rehash to speed up!
  188.     lsr.l    d0
  189.     move.l    d0,Hash.numTaken        ; Only if not rehashed, complete the increment.
  190.  
  191. ; Copy string to buffer.
  192.     clr.l    d7
  193.     move.w    .stringsize(pc),d7
  194.     movea.l    a2,a1                ; a1: current string
  195.     adda.l    d7,a1                ; Add stringlength.
  196.     addq    #4,a1                ; Add datalength. a1: next string
  197.     suba.l    Hash.bufferAdr,a1        ; a1=projected bufsize
  198.     cmpa.l    Hash.bufSize,a1
  199.     bhs.s    .rebuf
  200.  
  201. .copy:    move.l    d1,(a2)+            ; Copy data.
  202.     subq.w    #1,d7
  203. .cploop:move.b    (a6)+,(a2)+
  204.     dbf    d7,.cploop
  205.     clr.b    (a2)+
  206.     move.l    a2,Hash.nextStringAdr        ; Set new string address.
  207.  
  208. .success:
  209.     movem.l    (sp)+,d2-d7/a1-a6
  210.     moveq    #0,d0
  211.     rts
  212.  
  213. .rehash:bsr    Hash.reHash
  214.     move.l    d0,d2                ; d2.l=rehash resultcode
  215.     movea.l    a6,a0
  216.     move.w    .stringsize(pc),d0
  217.     tst.l    d2
  218.     beq.s    .redo
  219. ; Error, rehashing failed.
  220.     movem.l    (sp)+,d2-d7/a1-a6
  221.     moveq    #Hash.REHASH_FAILED,d0
  222.     rts
  223.  
  224. ; kill kill fuck kill fuck kill kill fuck kill fuck kill kill fuck kill kill
  225. .rebuf:    bsr    Hash.extendBuffer
  226.     movea.l    Hash.nextStringAdr,a2
  227.     tst.l    d0
  228.     beq.s    .copy
  229. .rebuf_failed:
  230.     movem.l    (sp)+,d2-d7/a1-a6
  231.     moveq    #Hash.REBUF_FAILED,d0
  232.     rts
  233.  
  234. .null_string:
  235.     movem.l    (sp)+,d2-d7/a1-a6
  236.     moveq    #Hash.NULL_STRING,d0
  237.     rts
  238.  
  239. .stringsize:
  240.     DC.W    0
  241.  
  242. ; INPUT:
  243. ; a0: string
  244. ; d0.w= string length
  245. ; OUTPUT:
  246. ; d1.l= data (crap if not found)
  247. Hash.get:
  248.     bsr.s    Hash.calcKey
  249.     tst.w    Hash.wasFound(pc)
  250.     bne.s    .ok
  251.     rts
  252. .ok:    movea.l    Hash.tableAdr,a0        ; a0: table
  253.     movea.l    (a0,d0.l*4),a0            ; a0: string
  254.     move.l    (a0),d1                ; d1.l=data
  255.     rts
  256.  
  257. ; INPUT:
  258. ; a0: string (nullterminated)
  259. ; OUTPUT:
  260. ; d1.l= data (crap if not found)
  261. Hash.get0:
  262.     bsr    Hash.calcKey0
  263.     tst.w    Hash.wasFound(pc)
  264.     bne.s    .ok
  265.     rts
  266. .ok:    movea.l    Hash.tableAdr,a0        ; a0: table
  267.     movea.l    (a0,d0.l*4),a0            ; a0: string
  268.     move.l    (a0),d1                ; d1.l=data
  269.     rts
  270.  
  271. ; Hashes and applies quadratic probing.
  272. ; INPUT:
  273. ; a0: string (need not be nullterminated)
  274. ; d0.w=stringlength
  275. ; OUTPUT:
  276. ; d0.l= >=0:key, <0:error
  277. Hash.calcKey:
  278.     movem.l    d1-d3/a0-a3,-(sp)
  279.     move.w    d0,d3
  280.     subq.w    #1,d0
  281.     ext.l    d0
  282.     bmi.s    .end
  283.  
  284. ; Hash the shit.
  285.     clr.l    d2
  286. .loop:    move.b    (a0)+,d1
  287.     eor.b    d1,d2
  288.     move.l    d2,d1
  289.     rol.l    d2,d2
  290.     eor.l    d1,d2
  291.     dbf    d0,.loop
  292.     clr.l    d1
  293.     divu.l    Hash.numEntries,d1:d2
  294.     move.l    d1,d0
  295.     suba.w    d3,a0                ; a0: string
  296.     subq.w    #1,d3
  297.  
  298. ; Apply quadratic probing to resolve mess..
  299.     moveq    #0,d1                ; d1.l=i[0]
  300.     movea.l    Hash.tableAdr,a2
  301. .ploop:    movea.l    a0,a3                ; a3: string
  302.     movea.l    (a2,d0.l*4),a1
  303.     tst.l    a1
  304.     sne    Hash.wasFound            ; Mark as 'not found'.
  305.     beq.s    .end                ; Vacant? Shove it in!
  306.     addq    #4,a1                ; a1: stored string
  307.     move.w    d3,d2
  308. .cloop:    cmpm.b    (a1)+,(a3)+
  309.     dbne    d2,.cloop
  310.     tst.w    d2                ; Whole searchstring done?
  311.     bpl.s    .next                ; no -> not found.
  312.     tst.b    (a1)                ; Whole dst. string done?
  313.     bne.s    .next                ; no -> not found.
  314.     seq    Hash.wasFound            ; Mark as 'found'.
  315.     bra.s    .end                ; String matches? Found!
  316.  
  317. .next:    addq.w    #1,d1                ; d1.l=i[n+1]=i[n]+1
  318.     move.l    d1,d2
  319.     add.l    d2,d2                ; d2.l=2*i[n+1]
  320.     subq.l    #1,d2                ; d2.l=2*i[n+1]-1
  321.     add.l    d2,d0                ; d0.l=pos[n+1]
  322.     cmp.l    Hash.numEntries,d0        ; Correct pos..
  323.     blt.s    .ploop
  324.     sub.l    Hash.numEntries,d0        
  325.     bra.s    .ploop    
  326.  
  327. .end:    movem.l    (sp)+,d1-d3/a0-a3
  328.     rts
  329.  
  330. ; INPUT:
  331. ; a0: string (nullterminated)
  332. ; OUTPUT:
  333. ; d0.l=key
  334. ; a0: end of string
  335. Hash.calcKey0:
  336.     movea.l    a0,a1
  337.     moveq    #-1,d0
  338. .loop:    addq.w    #1,d0
  339.     tst.b    (a1)+
  340.     bne.s    .loop
  341.     move.l    a1,-(sp)
  342.     bsr    Hash.calcKey
  343.     movea.l    (sp)+,a0
  344.     rts
  345.  
  346. ; OUTPUT:
  347. ; d0.l= 0:ok, <0:error (fatal, deinit required)
  348. Hash.reHash:
  349.     movem.l    d1-a6,-(sp)
  350.  
  351. ; Allocate new table.
  352.     move.l    Hash.numEntries,d0
  353.     add.l    d0,d0
  354.     bsr    Hash.nextPrime
  355.     move.l    d0,d7                ; d7.l= new #entries
  356.     move.l    d7,Hash.numEntries        ; Set new #entries.
  357.     lsl.l    #2,d0                ; d0*4
  358.     Malloc    d0
  359.     beq.s    .error
  360.  
  361. ; Clear new table.
  362.     movea.l    d0,a1                ; a1: new table
  363.     movea.l    d0,a2                ; a2: new table
  364.     clr.l    d0
  365. .cloop:    move.l    d0,(a1)+
  366.     subq.l    #1,d7
  367.     bne.s    .cloop
  368.  
  369. ; Rebuild table.
  370.     movea.l    Hash.tableAdr,a6        ; a6: old table
  371.     move.l    a2,Hash.tableAdr        ; Set new table.
  372.     movea.l    Hash.bufferAdr,a0        ; a0: strings
  373.     clr.l    d0
  374. .loop:    cmpa.l    Hash.nextStringAdr,a0
  375.     bhs.s    .rebuilt
  376.     movea.l    a0,a5                ; a5: data+string
  377.     addq    #4,a0                ; a0: string
  378.     bsr    Hash.calcKey0
  379.     move.l    a5,(a2,d0.l*4)            ; Store string address.
  380.     bra.s    .loop    
  381. .rebuilt:
  382.  
  383.     Mfree    a6                ; Free up old table.
  384.     movem.l    (sp)+,d1-a6
  385.     moveq    #0,d0
  386.     rts
  387. .error:    movem.l    (sp)+,d1-a6
  388.     moveq    #-1,d0
  389.     rts
  390.  
  391. ; OUTPUT:
  392. ; d0.l= 0:ok, <0:error
  393. Hash.extendBuffer:
  394.     movem.l    d1-a6,-(sp)
  395.  
  396. ; Allocate new space.
  397.     move.l    Hash.bufSize,d0            ; d0.l=old buffersize
  398.     add.l    d0,d0                ; d0.l=new buffersize = old buffersize * 2
  399.     move.l    d0,Hash.bufSize            ; Set new buffersize.
  400.     Malloc    d0
  401.     beq.s    .error
  402.  
  403. ; Copy old buffer to new.
  404.     movea.l    d0,a1                ; a1: new buf
  405.     movea.l    d0,a2                ; a2: new buf
  406.     movea.l    Hash.bufferAdr,a0        ; a0: old buf
  407.     movea.l    a0,a3                ; a3: old buf
  408.     move.l    Hash.nextStringAdr,d0
  409.     sub.l    a0,d0                ; d0.l=#bytes to copy
  410. .cploop:move.b    (a0)+,(a1)+
  411.     subq.l    #1,d0
  412.     bne.s    .cploop
  413.  
  414. ; Relocate table pointers.
  415.     movea.l    Hash.tableAdr,a0
  416.     move.l    Hash.numEntries,d7
  417. .loop:    move.l    (a0),d0
  418.     beq.s    .next
  419.     sub.l    a3,d0                ; d0.l=offset
  420.     add.l    a2,d0                ; d0.l=offset+new_base=new_adr
  421. .next:    move.l    d0,(a0)+            ; Store new address.
  422.     subq.l    #1,d7
  423.     bne.s    .loop
  424.  
  425. ; Set new addresses.
  426.     move.l    a1,Hash.nextStringAdr        ; Set new buffer end.
  427.     Mfree    Hash.bufferAdr            ; Free up old buffer.
  428.     move.l    a2,Hash.bufferAdr        ; Set new buffer.
  429.  
  430.     movem.l    (sp)+,d1-a6
  431.     moveq    #0,d0
  432.     rts
  433. .error:    movem.l    (sp)+,d1-a6
  434.     moveq    #-1,d0
  435.     rts
  436.  
  437. ; lame primalty tester
  438. ; INPUT:
  439. ; d0.w=num (0 extended)
  440. ; OUTPUT:
  441. ; d0.w=nextPrime(num)
  442. Hash.nextPrime:
  443.     movem.l    d1-d4,-(sp)
  444. ; First make it odd.
  445.     btst    #0,d0
  446.     bne.s    .odd
  447.     addq.w    #1,d0
  448.  
  449. .odd:    moveq    #1,d1
  450.     clr.l    d4
  451.  
  452. .loop:    addq.w    #2,d1
  453.     move.w    d1,d2
  454.     mulu.w    d2,d2
  455.     cmp.l    d0,d2
  456.     bhs.s    .end
  457.     move.l    d0,d3
  458.     divu.w    d1,d3                ; num mod d1
  459.     swap    d3                ; d3.w=rest
  460.     tst.w    d3                ; test rest
  461.     bne.s    .loop
  462.     moveq    #1,d4
  463.     bra.s    .loop                ; modulo 0 -> not prime -> try again!
  464.  
  465. .end:    addq.w    #2,d0                ; Try next number..
  466.     tst.l    d4                ; Number not prime?
  467.     bne.s    .odd                ; -> Try next!
  468.  
  469.     subq.w    #2,d0                ; Last num was okay..
  470.     movem.l    (sp)+,d1-d4
  471.     rts
  472.  
  473.     IFND    QDSP
  474.  
  475. Hash.string1:
  476.     DC.B    "bitch",0
  477. Hash.string2:
  478.     DC.B    "bitchass",0
  479. Hash.string3:
  480.     DC.B    "meuhBlah",0
  481. Hash.string4:
  482.     DC.B    "arggghhh",0
  483. Hash.string5:
  484.     DC.B    "teringneet",0
  485. Hash.string6:
  486.     DC.B    "mothafokka",0
  487. Hash.string7:
  488.     DC.B    "krijgdetering",0
  489. Hash.string8:
  490.     DC.B    "kloothommel",0
  491. Hash.string9:
  492.     DC.B    "unclefucker",0
  493.     EVEN
  494.  
  495.     ENDC
  496.  
  497.     BSS
  498.  
  499. Hash.bufSize:
  500.     DS.L    1
  501. Hash.tableAdr:
  502.     DS.L    1
  503. Hash.bufferAdr:
  504.     DS.L    1
  505. Hash.numEntries:                ; #slots
  506.     DS.L    1
  507. Hash.numTaken:                    ; #slots occupied
  508.     DS.L    1
  509. Hash.nextStringAdr:
  510.     DS.L    1
  511. Hash.wasFound:
  512.     DS.W    1
  513.  
  514. len:    ds.w    1
  515.