home *** CD-ROM | disk | FTP | other *** search
/ Euroscene 1 / Euroscene 1.iso / resource / shellsort.lha / shellsort.asm
Encoding:
Assembly Source File  |  1993-10-15  |  11.9 KB  |  480 lines
  1. ;i used asmone and trashemone
  2. ;*****************************************************************************
  3. ;exec.library
  4. allocmem    equ    -198
  5. freemem        equ    -210
  6. oldopenlibrary    equ    -408
  7. closelibrary    equ    -414
  8.  
  9. ;dos.library
  10. open        equ    -30
  11. close        equ    -36
  12. read        equ    -42
  13. write        equ    -48
  14. output        equ    -60
  15. lock        equ    -84
  16. unlock        equ    -90
  17. examine        equ    -102
  18.  
  19.  
  20.     movem.l    d1-d7/a1-a6,-(a7)    ;store regs
  21. ;-------------
  22.     move.l    $4.w,a6
  23.     movem.l    d0/a0,-(a7)        ;store temporary
  24.     lea    doslib,a1
  25.     jsr    oldopenlibrary(a6)
  26.     move.l    d0,a5
  27.     movem.l    (a7)+,d0/a0        ;regs back
  28.     move.l    a5,dosbase        ;store dos base
  29.  
  30.     cmp.l    #1,d0            ;if there is no input from CLI
  31.     beq.w    kraj            ;go to end
  32.     cmp.b    #$3f,(a0)        ;is first character '?'
  33.     beq.w    kraj
  34.     
  35.     move.l    a0,a2            ;store address of CLI input 
  36.     lea    buff,a1
  37.     bsr.w    string            ;read one text word
  38.     cmp.b    #"-",(a1)
  39.     bne.b    nista
  40.     move.b    #$ff,flag        ;set only flag for option '-n'
  41.     bra.b    nesta
  42. nista    move.b    #0,flag            ;reset flag
  43.     move.l    a2,a0            ;no options, bring back
  44. nesta    lea    ulaz,a1
  45.     bsr.w    string            ;read input file name
  46.     lea    izlaz,a1
  47.     bsr.w    string            ;read output file name
  48. ;***********************************************************************
  49.     jsr    output(a5)        ;take handle pointer
  50.     move.l    d0,d1
  51.     move.l    #reading,d2
  52.     moveq    #$0b,d3
  53.     jsr    write(a5)        ;write text "reading..."
  54.  
  55.     move.l    #$108,d0        ;264 bytes for FileInfoBlock
  56.     moveq    #00,d1
  57.     jsr    allocmem(a6)
  58.     move.l    d0,a4            ;store temporary
  59.  
  60.     move.l    #ulaz,d1
  61.     move.l    #-2,d2            ;shared lock
  62.     jsr    lock(a5)        ;lock
  63.  
  64.     tst.l    d0
  65.     beq.w    error1
  66.  
  67.     move.l    d0,-(a7)        ;store pointer
  68.     move.l    d0,d1            ;lock pointer
  69.     move.l    a4,d2            ;FileInfoBlock allocation
  70.     jsr    examine(a5)        ;examine file
  71.  
  72.     tst.l    d0
  73.     beq.w    error1
  74.     move.l    $7c(a4),size        ;store file length
  75.  
  76.     move.l    #$108,d0
  77.     move.l    a4,a1
  78.     jsr    freemem(a6)        ;free 264 bytes
  79.  
  80.     move.l    (a7)+,d1        ;take back lock pointer
  81.     jsr    unlock(a5)        ;unlock
  82. ;-------------
  83.     move.l    size,d0
  84.     moveq    #00,d1
  85.     jsr    allocmem(a6)        ;alocate place for input file
  86.  
  87.     move.l    d0,a4            ;store pointer
  88.     move.l    d0,source
  89.     move.l    size,d0
  90.     moveq    #00,d1
  91.     jsr    allocmem(a6)        ;alocate place for sorted file
  92.  
  93.     move.l    d0,dest            ;store pointer
  94. ;-------------
  95.     move.l    #ulaz,d1
  96.     move.l    #1005,d2
  97.     jsr    open(a5)        ;open input file
  98.  
  99.     tst.l    d0
  100.     beq.w    error1            ;on error, finish
  101.     move.l    d0,-(a7)        ;store file pointer
  102.  
  103.     move.l    d0,d1
  104.     move.l    a4,d2
  105.     move.l    size,d3
  106.     jsr    read(a5)        ;read input file
  107.  
  108.     tst.l    d0
  109.     beq.w    error1
  110.     move.l    d0,length        ;store number of bytes readed
  111.  
  112.     move.l    (a7)+,d1        ;take back file pointer
  113.     jsr    close(a5)        ;close input file
  114. ;*************************************************************************
  115.     clr.l    d5            ;lines counter
  116.     tst.b    flag            ;do we have option '-n'
  117.     bne.b    bb
  118.  
  119.     move.l    length,d0        ;read file length
  120.     moveq    #10,d3            ;LINE FEED
  121.     bra.b    ba
  122.  
  123. ba0    addq.l    #1,d5            ;lines counter++
  124. ba     subq.l    #1,d0            ;char counter--
  125.     tst.l    d0
  126.     bmi.b    otislo            ;have we read all chars
  127.     cmp.b    (a4)+,d3        ;is char LINE FEED
  128.     bne.b    ba            ;jump if not LF
  129.  
  130.     bra.b    ba0
  131. ;-------------
  132. bb    move.l    length,d0        ;read file length
  133.     moveq    #0,d2            ;clear counter (no. of chars in line)
  134.     moveq    #$0a,d3            ;LINE FEED
  135.     moveq    #$20,d1            ;SPACE
  136.     moveq    #01,d7
  137.     bra.b    b21
  138.  
  139. b11    subq.l    #1,d0            ;char counter--
  140.     addq.l    #1,a4            ;address++
  141.     tst.l    d0            ;is it end of file
  142.     bmi.b    otislo            ;if it is, go further
  143.  
  144. b21    cmp.b    (a4),d1            ;is char less than SPACE
  145.     bge.b    b11            ;it is, jump (SPACE is > than char)
  146.  
  147. bc     subq.l    #1,d0            ;char counter--
  148.     tst.l    d0
  149.     bmi.b    otislo
  150.     addq.b    #1,d2            ;chars in line counter++
  151.     cmp.b    (a4)+,d3        ;is it LINE FEED(end of line)
  152.     bne.b    bc            ;jump if not LF
  153.  
  154.     cmp.b    d7,d2            ;is line length 1 (only LF)
  155.     beq.b    bd            ;if it is, ignore it
  156.     addq.l    #1,d5            ;lines counter++
  157. bd    moveq    #0,d2            ;clear counter
  158.     bra.b    b21
  159. ;-------------
  160. otislo    move.l    d5,no_of_lines        ;store it
  161.     
  162.     move.l    d5,d0            ;no. of lines
  163.     lsl.l    #2,d0            ;divide by 4
  164.     addq.l    #4,d0            ;add 4 bytes
  165.     move.l    d0,size2
  166.     moveq    #00,d1
  167.     jsr    allocmem(a6)        ;alocate place for pointers on
  168.                     ;beginning of line
  169.     move.l    d0,a3            ;store pointer
  170.     move.l    d0,pointers1
  171.     move.l    source,a4
  172.     
  173.     tst.b    flag            ;check option
  174.     bne.b    aa
  175.     move.l    a4,(a3)+        ;first pointer is pointer on
  176.                     ;   first char in file 
  177. aa    move.l    no_of_lines,d0
  178.     moveq    #00,d1            ;alocate place for lenghts
  179.     jsr    allocmem(a6)        ;of lines
  180.  
  181.     move.l    d0,pointers2
  182. ;-------------
  183.     tst.b    flag            ;test flag
  184.     bne.w    read2
  185.  
  186.     move.l    length,d0        ;take file length
  187.     move.l    pointers2,a2        ;place for line pointers
  188.     moveq    #10,d3            ;LINE FEED
  189.     moveq    #0,d2            ;clear
  190.     bra.b    nije
  191.  
  192. ni    move.b    d2,(a2)+        ;store no of chars in line
  193.     move.l    a4,(a3)+        ;store next address as pointer
  194.     moveq    #0,d2            ;clear counter
  195.  
  196. nije     subq.l    #1,d0            ;char counter--
  197.     tst.l    d0            ;is it all ?
  198.     bmi.b    nema            ;if yes, finish this part
  199.     addq.b    #1,d2            ;chars in line counter++
  200.     cmp.b    (a4)+,d3        ;is it LINE FEED
  201.     bne.b    nije            ;jump if not LF
  202.  
  203.     bra.b    ni
  204. ;-------------
  205. read2    move.l    length,d0        ;take file length
  206.     move.l    d0,d5
  207.     move.l    pointers2,a2        ;place for line pointers
  208.     moveq    #0,d2            ;clear counter
  209.     moveq    #10,d3            ;LINE FEED
  210.     moveq    #32,d1            ;SPACE
  211.     moveq    #01,d7
  212.     bra.b    b2
  213.  
  214. era    moveq    #0,d2            ;clear counter
  215.     subq.l    #1,d5            ;char counter--
  216.     bra.b    b2
  217.         
  218. b1    subq.l    #1,d0            ;char counter--
  219.     tst.l    d0
  220.     bmi.b    nema2            ;is it EOF (jump if is)
  221.     addq.l    #1,a4            ;address++
  222.     subq.l    #1,d5            ;char counter--
  223.  
  224. b2    cmp.b    (a4),d1            ;is it less than SPACE
  225.     bge.b    b1            ;SPACE is greater, jump
  226.  
  227.     move.l    a4,a0            ;store address of line
  228.  
  229. nije2     subq.l    #1,d0            ;char counter--
  230.     tst.l    d0
  231.     bmi.b    nema2            ;is it EOF
  232.     addq.b    #1,d2            ;chars in line counter++
  233.     cmp.b    (a4)+,d3        ;is it LINE FEED (end of line)
  234.     bne.b    nije2            ;jump if not LF
  235.  
  236.     cmp.b    d7,d2            ;is line length 1,only LF
  237.     beq.b    era            ;if is, ignore it
  238.     move.b    d2,(a2)+        ;store no. of chars
  239.     move.l    a0,(a3)+        ;store next address as pointer
  240.     moveq    #0,d2            ;clear counter
  241.     bra.b    b2
  242. nema2    move.l    d5,length        ;store new length of file without
  243.                     ;chars that are ignored
  244. ;**********************************************************************
  245. nema    jsr    output(a5)
  246.     move.l    d0,d1
  247.     move.l    #sorting,d2
  248.     moveq    #$0f,d3
  249.     jsr    write(a5)        ;write text "sorting..."
  250.  
  251.     move.l    no_of_lines,a4        ;read no. of lines
  252.     move.l    a4,d0
  253.         
  254.     move.l    pointers1,a0        ;read address of pointers to source
  255.     move.l    pointers2,a3        ;read address where to put sorted pointers
  256.  
  257.     bra.b    a
  258.  
  259. ;d0=range, d1=i, d2=j, a4=n
  260. ;this variables are same as in algorithm i wrote at start of file
  261. zamjena    move.l    d4,a1            ;get addresses of
  262.     move.l    d5,a2            ;both operands
  263.     move.l    (a2),d4
  264.     move.l    (a1),(a2)        ;first pointer instead second
  265.     move.l    d4,(a1)            ;second pointer instead first
  266.  
  267.     move.l    d6,a1            ;read address of 1st operand
  268.     move.l    d7,a2            ;read address of 2nd operand
  269.     move.b    (a2),d4            ;swap no. of chars in lines
  270.     move.b    (a1),(a2)        ;for same lines as above
  271.     move.b    d4,(a1)
  272.     bra.b    dalje
  273.  
  274. a    lsr.l    #1,d0            ;range divide by 2
  275.     beq.b    gotovo            ;if x==0, finish sort
  276.  
  277.     move.l    d0,d1            ;i=range
  278.     subq.l    #1,d1            
  279.  
  280. b    addq.l    #1,d1            ;i++
  281.     cmp.l    a4,d1            ;is i==n
  282.     beq.b    a            ;if it is, jump
  283.  
  284.     move.l    d1,d2            ;j=i
  285. dalje    sub.l    d0,d2            ;j=i-range
  286.     bmi.b    b            ;if j<0, jump
  287.  
  288.     move.l    a3,d6            ;read addresses of lengths
  289.     add.l    d2,d6            ;   of lines
  290.     move.l    a3,d7            ;for both operands
  291.     add.l    d2,d7
  292.     add.l    d0,d7
  293.  
  294.     asl.l    #2,d2            ;d2=d2*4; for longs
  295.     asl.l    #2,d0            ;d0      -||-
  296.     move.l    a0,a1            ;a1=j-th element
  297.     add.l    d2,a1
  298.     move.l    a0,a2            ;a2=(j+range)-th element
  299.     add.l    d2,a2
  300.     add.l    d0,a2
  301.     move.l    a1,d4            ;store 1st pointer
  302.     move.l    a2,d5            ;store 2nd pointer
  303.     move.l    (a1),a1            ;store 1st operand address
  304.     move.l    (a2),a2            ;store 2nd operand address
  305.     asr.l    #2,d2            ;d2=d2/4
  306.     asr.l    #2,d0            ;d0=d0/4
  307.     
  308. ponovo    cmpm.b    (a1)+,(a2)+        ;compare two chars
  309.     bmi.b    zamjena            ;if 2nd<1st, change them
  310.     beq.b    ponovo            ;if 1st==2nd, check next
  311.     bra.b    b            ;if 1st<2nd, compare next two lines
  312. ;***********************************************************************
  313. gotovo    jsr    output(a5)
  314.     move.l    d0,d1
  315.     move.l    #writing,d2
  316.     moveq    #$0f,d3
  317.     jsr    write(a5)        ;write text "writing..."
  318.  
  319.     move.l    pointers1,a3        ;read start of sorted pointers
  320.     move.l    dest,a2            ;read destination address
  321.     move.l    pointers2,a0        ;read addr. of length of lines
  322.     move.l    no_of_lines,d2        ;read no. of lines
  323.  
  324.     move.b    #$fc,d1            ;mask for savingfirst 6 bits,
  325.                     ;to find no. of longs in line
  326.     moveq    #3,d3            ;3 bytes and  mask %00000011
  327.     moveq    #10,d4            ;LINE FEED    
  328.  
  329. jos    tst.l    d2            ;is lines counter==0
  330.     beq.b    next            ;yes, finish this part
  331.     move.l    (a3)+,a1        ;move pointer of actual line
  332.     subq.l    #1,d2            ;lines counter--
  333.     move.b    (a0)+,d0        ;length of line in bytes
  334.     cmp.b    d3,d0            ;compare with 3
  335.     ble.b    x            ;if length <= 3, jump
  336.  
  337. long    move.b    d0,d6            ;store 
  338.     and.b    d1,d0            ;clear no. of chars with mask %11111100
  339.     lsr.b    #2,d0            ;and eliminate 2 last right bits
  340.  
  341. jos2    move.l    (a1)+,(a2)+        ;copy necessary no. of longs
  342.     subq.b    #1,d0            ;no. of longs--
  343.     bne.b    jos2            ;loop
  344.     
  345.     and.b    d3,d6            ;store 2 right bits
  346.     beq.b    jos            ;if there is no chars, continue
  347.  
  348. x    move.b    (a1),(a2)+        ;copy char
  349.     move.b    (a1)+,d6        ;read next char
  350.     cmp.b    d4,d6            ;is it LINE FEED,
  351.     bne.b    x            ;no, copy more chars
  352.     bra.b    jos            ;yes, continue
  353.  
  354. ;***********************************************************************
  355. next    move.l    #izlaz,d1
  356.     move.l    #1006,d2
  357.     jsr    open(a5)        ;open output file
  358.     tst.l    d0
  359.     beq.w    error2            ;output file error
  360. ;-------------
  361.     move.l    d0,d1            ;file pointer
  362.     move.l    d0,-(a7)        ;store
  363.     move.l    dest,d2            ;address
  364.     move.l    length,d3        ;file length
  365.     jsr    write(a5)        ;write output file
  366. ;-------------
  367.     move.l    (a7)+,d1
  368.     jsr    close(a5)        ;close output file
  369. ;-------------
  370.     jsr    output(a5)
  371.     move.l    d0,d1
  372.     move.l    #done,d2        ;write last message
  373.     moveq    #$10,d3
  374.     jsr    write(a5)
  375.     
  376. dealloc    move.l    size,d0
  377.     move.l    source,a1
  378.     jsr    freemem(a6)        ;free 1st memory
  379. ;-------------
  380.     move.l    size,d0
  381.     move.l    dest,a1
  382.     jsr    freemem(a6)        ;free 2nd memory
  383. ;-------------
  384.     move.l    size2,d0
  385.     move.l    pointers1,a1
  386.     jsr    freemem(a6)        ;free place for pointers
  387. ;-------------
  388.     move.l    no_of_lines,d0
  389.     move.l    pointers2,a1        ;free place for line lengths
  390.     jsr    freemem(a6)
  391. ;-------------
  392. kraj2    move.l    a5,a1
  393.     jsr    closelibrary(a6)    ;close dos.library
  394.     movem.l    (a7)+,d1-d7/a1-a6
  395.     rts
  396. ;***********************************************************************
  397. kraj    bsr.b    ekran            ;pointer in d1
  398.     move.l    #logo,d2
  399.     move.l    #$ee,d3
  400.     jsr    write(a5)        ;write text message
  401.  
  402.     jmp    kraj2
  403.  
  404. error1    bsr.b    ekran
  405.     move.l    #greska1,d2
  406.     moveq    #22,d3
  407.     jsr    write(a5)        ;write text input error
  408.  
  409.     jmp    dealloc
  410.  
  411. error2    bsr.b    ekran
  412.     move.l    #greska2,d2
  413.     moveq    #22,d3
  414.     jsr    write(a5)        ;write text output error
  415.  
  416.     jmp    dealloc
  417.  
  418.  
  419. ekran    jsr    output(a5)
  420.     tst.l    d0
  421.     beq.b    .ekr2
  422.     move.l    d0,d1
  423.     rts
  424.  
  425. .ekr2    move.l    (a7)+,d0        ;return address pick from stack
  426.     jmp    dealloc
  427.  
  428. string    movem.l    d1-d3/a1,-(a7)        ;store regs
  429.  
  430.     moveq    #10,d1            ;LINE FEED
  431.     moveq    #32,d2            ;SPACE
  432.     clr.l    d0            ;clear counter
  433. .a    move.b    (a0),d3
  434.     cmp.b    d2,d3            ;is it SPACE
  435.     beq.b    .b
  436.     cmp.b    d1,d3            ;is it LINE FEED
  437.     beq.b    .c
  438.     tst.l    d3            ;is it NULL
  439.     beq.b    .c
  440.     move.b    (a0)+,(a1)+        ;copy char
  441.     addq.l    #1,d0            ;counter++
  442.     bra.b    .a
  443. .b    addq.l    #1,a0            ;address++
  444.     cmp.b    (a0),d2            ;is it another SPACE
  445.     beq.b    .b            ;if not, stay here
  446. .c    clr.b    (a1)            ;put NULL at the end of string
  447.     addq.l    #1,d0            ;counter++
  448.     movem.l    (a7)+,d1-d3/a1        ;bring back regs
  449.     rts
  450.  
  451. ;------------------------------------------------------------------------------    
  452. doslib    dc.b    "dos.library",0
  453. ulaz    ds.b    40
  454. izlaz    ds.b    40
  455. buff    ds.b    40
  456. logo    dc.b    10,"Shellsort V1.12 ",10                ;18
  457.     dc.b    "   Made by ONE MAN GANG",10                ;24
  458.     dc.b    "Herendic Drazen",10                    ;16
  459.     dc.b    "26. lipanj 9",10,"43240 CAZMA",10,"CROATIA",10,10    ;34
  460.     dc.b    "USAGE: Shellsort [-n] input_file output_file ",10    ;46
  461.     dc.b    "  -n leading spaces and control characters are ignored",10,0 ;56
  462.     dc.b    "     (tabs, line feeds, form feeds, etc.)",10,10,0    ;44
  463. ;         1---5----0----5----0----5----0----5----0----5----0
  464. reading    dc.b    "Reading...",0,0
  465. sorting    dc.b    $9b,$31,$30,$44,"Sorting...",0,0
  466. writing    dc.b    $9b,$31,$30,$44,"Writing...",0,0
  467. done    dc.b    $9b,$31,$30,$44,"Done !    ",10,0
  468. greska1    dc.b    10,"Input file error ! ",10,0
  469. greska2    dc.b    10,"Output file error !",10,0
  470. dosbase    dc.l    0
  471. length    dc.l    0        ;length of file
  472. source    dc.l    0        ;address where file is loaded
  473. dest    dc.l    0        ;address where sorted file is stored
  474. pointers1    dc.l    0    ;array of pointers to start of line
  475. pointers2    dc.l    0    ;array of pointers on lengths of lines
  476. no_of_lines    dc.l    0    ;no. of lines=no. of pointers
  477. flag    dc.b    0,0        ;for option '-n'
  478. size    dc.l    0
  479. size2    dc.l    0
  480.