Flameman/m68ec0x0IDP

From eLinux.org
< Flameman
Revision as of 03:10, 19 August 2009 by Flameman (talk | contribs) (proof)
Jump to: navigation, search

EARLY PROOF VERSION OF THIS PAGE

m68ec0x0idp, dream, history, project

http://www.netbsd.org/docs/Hardware/Chips/Motorola/

I bought "BYTE magazine September 1987"; there is a sweet article about 68k & unix.

Byte68k.jpg

Today MOTOROLA semiconductor group is sold to Freescale. The so called "company evolution" .... Happened at the end of 2004. When Motorola was running the semiconductors desk, i was provided this IDP board as "68k learner". Since 1999 i have been looking around for the board that i'd like to develop in my lowest priority free time. She eats 2.5A, so at 5V that means 13Watt .... this because she has a lot of fun and troubles


m68k OS

1985: Terra Nova Communications: OS design

Created real-time multiuser OS for dialup conferencing. Kernel source published in Dr. Dobb's Journal (1/86). Innovative interface inspired hundreds of similar systems. One of the first tree-structured BBS systems. 68K asm, multitasking kernel, custom memory manager, custom disk I/O manager, custom serial drivers.

;
;       Terra Nova Communications multi-tasking kernel
;       Initialization and task-switcher
;
;       Note: this is not intended to be a complete listing.  It's only
;       a sample of some of the techniques used in our system.
;

                PSECT   Kernel
       
;              External symbols (defined in other code segments)
                EXTERN  VecTable, ;vector table for hardware vector list
                        JMPTable,       ;jump table for system calls
                        JMPTabLen,      ;length of jump table in longwords
                        KernEnd,        ;end of kernel code item in heap
                        IOInit,  ;our private I/O initialization routine
                        HeapInit,       ;our private heap initialization
                        SysInit,        ;system variable initializer
                        SysConMon,      ;entry point for system console
                                        ;monitor task
                        HeapMunger,     ;entry point for heap munger task
                        DiskMunger      ;entry point for disk munger task

;              Entry points in this module (referenced from elsewhere)
                ENTRY   Start,    ;primary entry point to boot our OS
                        ConSwitch,      ;main context switcher
                        ConSwSleep      ;alternate context switcher (puts
                                        ;calling task to sleep)

;              Include files (mostly equates)
                INCLUDE SysEqu      ;contains the low-memory absolute
                                        ;address equates (jump table, etc)
                INCLUDE HeapDef    ;defines the heap data structure
                INCLUDE SysIO        ;contains hardware I/O equates

;              Miscellaneous storage
CodeHeap        DS.L    8      ;heap header for kernel heap item
StackEnd        DS.L    40    ;system stack before tasking starts
StackBegin      DS.L  0  ;top of startup stack area

;              Pre-tasking initialization
;              this code works in single-task mode
;              prior to the invocation of the context switcher
Start         ;Initial entry.  Calling operating system is still
                      ;alive and kicking at this point.
TakeOver        LEA     ReEntry,A1   ;point to re-entry instruction
                MOVE.L  A1,$20.W  ;move short absolute to the vector
                                        ;for privilege exceptions
                MOVE    USP,A0            ;try a privileged instruction.  If it
                        ;works, then we're in priv. mode. If not, then trap to
                      ;ReEntry and be in privileged mode anyway
ReEntry  LEA      StackBegin,A7 ;set up initial stack

;              Turn off all interrupts in the system
;              Note: this is device-specific code.
;              The labels in the operand fields are from our own
;              SysIO include file.
                CLR.B   FDCIntMask ;clear floppy disk & system console
                CLR.B   HDIntMask  ;clear hard disk completion int. mask
                CLR.B   SerIO1IntMask      ;clear serial boards
                CLR.B   SerIO2IntMask

;              Initialize the vector table
;              Copy the vectors from an assembled table (in another module)
;              into the actual hardware vector list in low RAM
                LEA     VecTable,A0  ;source (in another code segment)
                LEA     $0.W,A1            ;destination (begins at $00 0000)
                MOVE    #191,D7          ;192 longwords to move
VecMove  MOVE.L   (A0)+,(A1)+        ;move a longword
                DBRA    D7,VecMove  ;repeat till done (fast loop on 68010)

;              Copy system routine JMP table from assembled object code (in
;              another module) to low memory jump table, where everyone
;              can get at them.
                LEA     JMPTable,A0  ;source
                LEA     System.W,A1  ;dest. (name of first system call in
                        ;the jump table.  "System" is from the SysEqu include
                      ;file.  It's the context switcher)
                MOVE    #JMPTabLen/4,D7     ;number of longwords to move
JPTMove  MOVE.L   (A0)+,(A1)+        ;move a longword
                DBRA    D7,JPTMove  ;repeat till done (fast loop on 68010)

;              Clear low memory to zero (between jmp table and kernel)
                LEA     StackEnd,A1  ;point to top of destination
                        ;and bottom of destination (end of the jump table)
                LEA     System+JMPTabLen.W,A0
                SUBA    A0,A1              ;calculate the length
                MOVE.L  A1,D7          ;move to D7 for counting
                LSR.L   #4,D7           ;divide by 16 for 16-byte blocks
LowClr    CLR.L     (A0)+                ;clear 16 bytes, quickly
                CLR.L   (A0)+
                CLR.L   (A0)+
                CLR.L   (A0)+
                DBRA    D7,LowClr   ;do it until done.

;              Clear high memory to zero (between kernel and end of RAM)
;              (RAMEnd is first byte beyond RAM, defined in SysEqu)
                LEA     RAMEnd,A1    ;point to top of destination
                        ;and bottom of destination (end of the jump table)
                LEA     KernEnd,A0
                SUBA    A0,A1              ;calc the length
                MOVE.L  A1,D7          ;move to D7 for counting
                LSR.L   #4,D7           ;divide by 16 for 16-byte blocks
HiClr      CLR.L      (A0)+  ;clear 16 bytes, quickly
                CLR.L   (A0)+
                CLR.L   (A0)+
                CLR.L   (A0)+
                DBRA    D7,HiClr    ;do it until done.

;              Initialize all of the primary I/O devices
;              Note: this is a device specific routine not treated in the article.
                JSR     IOInit
       
;              Initialize the heap
;              Note: this is a routine in the heap manager, which creates
;              valid heap headers for the three initial heap items discussed
;              in the text: the deletion below the kernel, the kernel code
;              item, and the deletion above the kernel.
                JSR     HeapInit

;              Initialize the system zone of low memory
;              Note: this sets up the TCB and master handle arrays, as
;              discussed in the text, as well as initializing the time of day
;              and the date and the other miscellaneous system values.
                JSR     SysInit

;              Spawn off the initial tasks
;              This will create TCBs and TData items for the tasks, but won't
;              invoke them.  They're invoked only by the context switcher.
                LEA     SysConMon,A0 ;point to system console entry point
                MOVE.L  #4096,D0  ;tell it how much RAM for TData
                JSR     Spawn                ;jump through jump table entry
                        ;("Spawn" is a jump table equate in SysEqu)
                LEA     HeapMunger,A0        ;spawn the heap munger
                MOVE.L  #512,D0      ;heap munger's TData size
                JSR     Spawn
                LEA     DiskMunger,A0        ;Spawn the disk munger
                MOVE.L  #8192,D0  ;(TData includes one disk buffer)
                JSR     Spawn

                LEA     TCB1.W,A2    ;get address of first TCB in array
                                        ;(TCB1 is defined in SysEqu)
                BRA.S   ConSw1          ;now start the context switcher!

;              Context Switcher: primary version
;              Simple task-switch, nothing fancy.
;              SysFlags is a low-RAM system flag byte, defined in SysEqu.
;              The data structure for the TData item is defined in SysEqu.
;              The data structure for the TCB is defined in SysEqu.
ConSwitch       BTST   #StopSys,SysFlags.W ;task switching inhibited?
                BNE.S   ConSwX          ;yes, exit back to caller
                MOVE.L  OurTCB(A5),A0     ;get TCB address from TData
                SUBA.L  A5,SP          ;subtract TData base addr from stack
                MOVE.L  SP,TCBSP(A0)      ;save relative displacement in TCB

                MOVE.L  TCBNxt(A0),A2     ;get address of next TCB
ConSw1    MOVE.L    TCBA5(A2),A5        ;get new TData base address
                MOVE.L  TCBSP(A2),SP      ;get stack relative displacement
                ADDA.L  A5,SP          ;restore absolute address
ConSwX    RTS                     ;return to next task

;              Context Switcher: alternate version
;              Put the calling task to sleep.
ConSwSleep      BTST  #StopSys,SysFlags.W ;task switching inhibited?
                BNE.S   ConSwX          ;yes, exit back to caller
                                        ;without going to sleep
                MOVE.L  OurTCB(A5),A0     ;get TCB address from TData
                SUBA.L  A5,SP          ;subtract TData base addr from stack
                MOVE.L  SP,TCBSP(A0)      ;save relative displacement in TCB

                MOVE.L  TCBNxt(A0),A2     ;get address of next TCB
                MOVE.L  TCBPrev(A0),A1    ;get addr of previous TCB
                MOVE.L  A2,TCBNxt(A1)     ;close the pointers around the now-
                MOVE.L  A1,TCBPrev(A2)    ;sleeping task.
                MOVE.B  #Sleep,TCBState(A0) ;mark it as asleep

                MOVE.L  TCBA5(A2),A5      ;get new TData base address
                MOVE.L  TCBSP(A2),SP      ;get stack relative displacement
                ADDA.L  A5,SP          ;restore absolute address
                RTS               ;return to next task 


1985: Steve Passe Kernel for the MC68000

1987: "BYTE magazine September 1987, unix system design with m68k"

the m68ec0x0idp board

About the motorola board the motorola board is "IDP68EC0x0" part number

M68ec0xIDP-idea.jpg

On the board there are the following devices:

  • MC68EC000 CPU module 12.5Mhz
  • MC68EC060 CPU module 25Mhz
  • MC68681 (dual uart)
  • MC68230 (PIT port and timer)
  • DS7 (display 7 segment)
  • M48 (RTC)
  • 2/8MByte DRAM

i'm working around this devices

  • HD44780 (display 2x20 alphanumeric)
  • T6969 (display graphics)
  • I2C bus adapter PSX pad adapter
  • IDE-HD adapter new desin keyboard (developped around apple-newton-kb and dreamcast-jappanese-kb)

on the board i'm running

  • ucos/2 (it does not require a MMU, the 68EC000 has not, the 68060 has MMU and FPU)

An image of the board

M68ec0x0IDP.jpg

M68EC0x0 Integrated Development Platform version 3.1 July 1994

the board was made in 1992, and in 2002 costs $950, with a student reduce price i payed half the half: $250 ($90 surface shipping included) .


expanding RAM

Unfortunately the board is equipped with 2Mbyte of DRAM that can be expanded to 8Mbyte with this obsolete DRAM-array 1Mx32 (4Mbytes) for a total of 8Mbyte on board

- MCM54400AZ70 - MCM524256AZ70 package 100 MIL ZIP -

!!!!!!!!!!!!!!!!! ONLY ZIP PACKAGE !!!!!!!!!!!!!!!! 
MCM54400AZ70 ZIP pin assignments 


 * * * * * * * * * *
* * * * * * * * * * 


1 = !G 
2 = ! CAS 
3 = DQ2 
4 = DQ3 
5 = Vss 
6 = DQ0 
7 = DQ1 
8 = !W 
9 = !RAS 
10 = A9 
11 = A0 
12 = A1 
13 = A2 
14 = A3 
15 = Vcc 
16 = A4 
17 = A5 
18 = A6 
19 = A7 
20 = A8 

adding a peripheral: I/O module

The board has 6 x 16Mb addressable IDP buses: if the user wants to make a I/O module, the user should contact Motorola by writing to the address listed in "bus timing"

  • bus timing for information on M68EC0x0IDP bus timing, write the following adrress: Motorola High-Performance MPU division ATTN:
IDP Technical Support Mail Stop OE-33 6501 William Cannon Drive West 
Austin Texas 78735-8598 USA hi

clock sync

mc88915 or mc88916 is required in order to sync the module clock to the master clock

The meaning of DTACK Grounded

"DTACK" is

  • the name of a pin on the Motorolla 68000 CPU that informed the CPU that data was ready to be read from memory. If a system had fast enough memory, this pin could be connected directly to the ground plane (or "grounded") to produce the fastest-possible memory read time.
  • the signal from the memory system to the 68000 indicating “Yup, you can complete that memory cycle now,” and simply stapling it to ground means you’ve built a system with as few memory waits as you can.

I recall the DTACK Grounded boards were insanely expensive because they used a metric boatload of static RAM, but they ran as fast as raped apes


DTACK Revisited: fsm

the IDP bus requires a complex protocol, so a fsm machine is required in order to handle it: a cpld is fine for that

dynamic bus sizer

the IDP bus is 32bit, "mc68150" is a "dynamic bus sizer" chip made by Motorola for MC68040/MC68060: it may be a solution when you have a 32bit cpu and 8bit peripherals

Floating the Point

It was obvious from the first that while the 68000 was a really fast integer processor, it needed an FP math accelerator like the Intel 8087. Big M had in fact announced that it would ship such a part for the 68K in 1982, but it was vaporware until mid-1985.

Meanwhile, National Semiconductor developed a line of 68K-like processors, the 32000 series. NS used separate teams to develop the integer CPU and the FPU chips. The CPUs remained heavily bug-ridden for a long time. But when the 16032 FPU appeared in mid-1983, it worked.

Having learned from my original 68K experience, I carefully studied the 16032 data sheet and decided the FPU would (unlike Intel's 8087) easily interface with the 68K. So my little company built up a test jig using 3M's neat prototyping kit and guess what--it worked. But, unlike what the 16032 data sheet said, the FPU had to be run using a synchronous clock.

I published all this information in newsletter #24 (October 24, 1983), including a photograph of the prototype board. I contacted Stan Baker about this, and Stan's popular hardware column in Electronic Engineering Times reported that the 68K and the National Semi FP chip were compatible and a lot faster than Intel's x86 + 8087 combo. My next newsletter carried a photo and complete schematic of our second, simplified prototype. Soon we were selling production boards, one of which accepted up to three 16032s.

I thought Big M would be happy; FP support for the 68K now was readily available. Wrong. Big M folk were furious with me; they wanted everybody to wait for their 68881 to arrive. I thought National Semi would be happy because here was another market for its FP chip. Wrong. National Semi's minions were peeved because they didn't want its FPU used to support 68K-based systems. Intel was understandably unhappy. For a while there I screened my mail for letter bombs.

(National Semi told everybody that I didn't know what I was talking about; the 16032 was too an asynchronous part. Five months later, the data sheet was quietly changed to require synchronous operation. Tsk.)


proof

our motorola 68xxx dev board has a synch.bus.It can be handled only by a Finite State Machine (FSM) so we first look for a low cost CPLD/FPGA solution. too expensive, too much complicate. So now the project is based on a RAM-tiny-FSM: 4 input, 4 output, 16 states. The RAM is loaded with the bytestream at the boottime by a PIC that copy an I2C_EEPROM into the RAM. The project consists on the compiler (that make the bytestream image to be loaded to the eeprom, from a simil-C source) and the little board. I estimated that this TINY-FSM is able to work with a clock up to 25Mhz using old PC cache (15 ns) If you are interested we can collaborate about this project, about the hardware and about the software developping. Hello Adrian, It is nice to hear from you. I am glad that the 680x0 books I sent you are useful in your project. > i'm planning to develop a ROM/RAM tiny file-system What type of file system is this? Is it based on an existing file system such as MS-DOS, or something completely new? I have an interest in file systems, that is why I ask. FYI, the UCSD Pascal system has a very simple file system that support a fixed number of files (77). The file system is just a very simple array of file entries. Each file entry has a fixed width format similar to: file name (length byte + name characters) file type file creation date file modification date starting block ending block > the shell is ready as beta. > Would you like to try it under windows ? if so it will recompiled for > 80386 as a normal dos program. I would like to try this. Please compile for windows and let me know how to get it. Concerning the 680x0 IDP, try the following internet sites, they may have some information about this board's bus: http://www.faqs.org/faqs/motorola/68k-chips-faq/ http://archive.comlab.ox.ac.uk/cards/m68kfaq.html > a friend of mine went to Santa FE last weeks He should have contacted me, that would be fun. I live in Santa Fe in the north part. I have been here for about 10 years. Ciao >Subject: Re: Apple Lisa and Macintosh schematics >Date: Sun, May 25, 2003, 3:51 PM > HI !!!! luky to see you again ! > the book ? i'm developping a lot with "68000 family reference" > i'm programming a 680x0 emulator to deassembly with simulation path > .... yeh i'd like to hack and grap software secret to improve my > assembler. > I'm using my "68EC000 IDP board" rom with "MON68" monitor debugger > ..... my simultaor simulate the whole board using this rom. > In this way i can speed up download .... (that are reduced to a poor > file copy, because there is no real UART 9600 bps transfer .... just a > superfast 44MB/sec harddisk file copy .... the secret iis that the > memory is a file) > about hardware ? i'm planning to develop my board around a 68030, using > your "68030 reference book" ..... i'm planning just to use only 8bit > data bus ..... just 1 Kb Rom 1 64Kb Ram .... a HD44780 20x4 char > alphanumeric display and a 9600bps UART. > the firmware will be "PERVASIVE" : i mean that i'm planning to develop > a ROM/RAM tiny file-system, a nano kernel working with tasks (no > process or thread) ..... > well i'm learning a lot from your books .... i'm fully reading the SAMS > 68010-68020 primer .... that helps me a lot with the simulator > dettails. > wow that is all for now. > ah, yah i forget: the shell is ready as beta. > Would you like to try it under windows ? if so it will recompiled for > 80386 as a normal dos program. > I shocked myself porting it to my 68EC000 idp board .... and to a real > nintendo GameBoy > (this last one it was done for fun ..... i friend of mine told me that > was impossinble ..... but i did it) > any probelm ? > yes, to be honest a lot .... but the main one is that i have no > documentation about the bus of my "motorola 68EC0x0IDP integrated > development platform" ..... i bought it form Motorola (for $940) and > there is a documentation-book where it is written: > if you need documentation about the "IDP bus timing" please write to > "motorola Austin Texas" > i did as written nobody answared me .... i email motorola digitalDNA > .... the answared that the platform is obsoleted and that in their > server there is no documentation. > They suggest to use an oscilloscope to probe signal's timing from the > IDP bus ..... that is too hard for me for just a reason: i have no > oscilloscope .... and at school we have virtual one (done by LabView > and an acquisition board plugged inside PC) .... no goods for what i > need to do. > why i need this ? because the IDP bus is not standard and it is 25Mhz > syncronous ..... not so easy. > I'd like to plug an hard-disk to improve my file-system from tiny to > large (400MB 1GB) > that is really all since last time ... > and you ? how are you ? > a friend of mine went to SataFE last weeks ..... luky is him !!! > cool sun, cool place and people .... > and you what do you say ? > (p.s. where are you exactly ?) > best regards >>Hi Adrian, >>Have the Motorola 680x0 books been useful to your electrical engineering >>school work in Italia? Does the 68040 CPU chip work? Greetings, I haven't heard anything. I gave them your email address so you might get some mail directly. Also, I posted a request for the info on comp.sys.m68k Take a look: http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&group=comp.sys.m68k&selm=4163811b.0402201732.5b0d397%40posting.google.com So check this web page from time to time to see if someone replies. Good Luck, > hi, >> [*] bus timing > for information on M68EC0x0IDP bus timing, write the > >> following adrress: > >> Motorola > >> High-Performance MPU division > >> ATTN: IDP Technical Support > any news about this ??? > i can't find nothing on newsgroup. > Does your motorola friend have this information ? > or somebody know something about the board ? > best regards Greetings, Yes, I remember, how are you? Motorola is a very big company and the semiconductor division was just a small part. In fact, in the beginning it was set up to supply parts to the rest of the company. But it turned out that they sold most of their parts to other companies, and they made Motorola a lot of money for many years. But in the last several years the semiconductor division has been loosing money, so motorola decided to spin it off as a separate company. Now the must make money or go out of business! -mark- wrote: > hi, > do you remember me ? > i'm the boy you sold the "68060 die photos" > today i was shocked: "motorola semiconductors" has > been changed into "Freescale" > and all customers support of old "motorola digital > DNA" has automatically closed. what do you think is happening ? > is motorola in a big money jam ? > i contact the old "motorola digital DNA" to have informations about > "mc68150 dynamic bus sizer chip" freescale answared me ..... > (that it has no data-sheet) > what do you think ? > best regards I need precisely the functionality you are describing to test programs written for the ColdFire 5407 without the actual hardware. The code would only be used to create a tool for my use in testing and debugging my embedded code. My current project is an embedded system for testing proprietary electronic devices. Having an emulator would be invaluable during development and testing. If you could share your code with me I would certainly be willing to forward any support I add for the ColdFire back to you, if you like. If you can't share the actual code, I understand--I just had to ask--this sounds like it would be so helpful. Thanks, Chris -----Original Message----- Sent: Wednesday, September 03, 2003 3:00 PM Subject: Re: reverse assembler >Does your C program actually emulate the 68K? Yes, not the whole iset, i have to code it, i have no much time. However the demo i show to my teacher is able to run a "hello world" program that prints to a real HD44780 by re-defining trap 15 to a virtual device (that on the real board is a MC68230) that handles LPT where the display is attached. I planned to emulate 68000, 68020, 68030, 68040, 68060. I don't know how to handle MMU, now. however i'm working around 68000 and i have to test the ALU condition code register: there are no good tests in motorola books, i don't understand some dettails like MUL-U MUL-S condition code affections. >it sounds as if that is what you have--more than a mere disassembler. this because we code a lot of software, and because we did it aim for a lot of goal. The shell, the tini-filesystem and the "reverse-assembler" i don't like "disassembler" term because i mere de-asm is a program that jumps back your binary. My reverse-assembler emulate a binary into a virtual machine showing register contents step by step. I mean that i can obtain a file where you can easily track the register- values during the running. In this case the goal is the need: we have to code and test programs but we have to test them on a real 68000 board, the school's one, and unfortunatly we can't access to it when we want ... we have no much time and we have no money to buy a personal board. So we code an emulator to have the board in our portable PC. The real board is hard to be de-bugged ... because we can't track the memory or stop the CPU to analyze ... we code the emulator to allow this. >In your first post you asked if anyone was intrerested--if this is the case, >I am very interested--I need something like this to help me through my >>current project! what is your project about ??? how can my project help you ? which CPU should it be for ? >Would you consider sharing that code with me? it may be, i have to ask my teacher and my team. I remember you we are using ANSI crude C (borland Turbo C 3.0 for DOS) however the shell is portable to UNIX and we ported it using Gcc and HP-C89. what we really need now is a good 68K compiler. We hack Sierra C 68K, it works well but it is only for 68000, and it need windows. we will try to make a gcc-68K cross compiler for our HP-712 HPUX 11.00 best regards

Simulated Recursion

Recursion is a powerful tool for attacking problems where questions are repeated and the same actions are performed. C and Pascal allow recursion, but languages like COBOL generally forbid it.

In the early 1960s, C.A. Hoare developed the Quicksort sorting process. Quicksort divides the data into successively smaller groups. In itself this does not sound very impressive, but tests show that Quicksort can sort large volumes of data tens or hundreds of times faster than most commonly used algorithms. However, there is a problem.

Quicksort uses recursion, the process by which a procedure or a function calls itself. Recursion is very powerful in attacking problems where the same questions are repeated and the same actions are performed, but with each set of actions working with the result of a prior step. Examinations of data structures such as linked lists and trees are ideally suited for recursive programming. In languages such as C or Pascal, recursion is allowed, but languages like Cobol generally forbid recursion. A way around language limitations is to simulate recursion in a manner that can be coded in almost all programming languages.

A recursed program examines and acts upon data until it arrives at a point where logic suggests that there is a new set of data, ready to be acted upon by a new copy of the program being executed. At this point, the program calls itself. Normally this calling passes the new data to be processed by the next iteration. Eventually, the logic dictates that further recursion is unnecessary, and the current active version of the code falls out the bottom, returning to execute the instruction following the one that issued the call in the prior iteration of the recursive module. As each copy of the code finishes, it transmits information back to the calling copy. When control is finally passed to the original copy of the recursive module, falling out the bottom terminates the recursive process.

Simulating Recursion

Knowing the process by which recursion passes data upward and downward through the called modules, you can isolate and preserve the variables unique to each recursive step and simply loop a given piece of code to achieve simulated recursion. Since looping would start the code process at the same place each time, you must keep a place marker, indicating just where to begin the processing of the current iteration.

The data used by each iterative step can be in any form and is a function of the programming requirements. A binary switch is probably the best form for a place marker. A combination of the required variable data and a place marker form a snapshot of the conditions during any step of the recursion. You should construct a table where snapshots can be stored. A pointer to this stack of snapshots allows the program to select the appropriate set of values for a particular iteration of the recursive process. The depth of the stack must be such that it can contain all the steps necessary to achieve the objective of the program being executed.

Simulated Recursion in Quicksort Example

The examples I present here demonstrate simulated recursion Quicksort in a Cobol program. This is one of the most hostile and awkward environments in which to do recursive programming. The idea is, "If we can do it here, we can do it anywhere." The data portion of Quicksort would look like Listing One.

In Listing One, a table of 32,000 100-byte entries is the data to be sorted. SWAP-ELEMENT and PIVOT-VALUE represent scratch work areas required to hold individual table entries from time to time. The WORKING-INDEXES point to table entries and, as such, are full-word integers. FURST and LAAST are pointers to the first and last table entries in a group currently under consideration. The size and location of that group changes constantly during the progress of Quicksort.

HOW-RETURN is the place marker enabling the program to begin processing at the correct place when reentering the looped code. The place-marker concept is critical to enabling fixed, looped code to emulate recursive processing.

The TABLE-OF-INDEXES is a stack of WORKING-INDEXES. As the program progresses downward (calling another iteration of QUICKSORT) or upward (returning to a prior iteration) the values for pointers and place markers are saved or retrieved. Every occurrence within the TABLE-OF-INDEXES is one set of WORKING-INDEXES. The SESSION-INDEX is the pointer to the set of values currently being used. LEFT and RIGHT-INDEX are working pointers used during each phase of Quicksort.

Listing Two initializes Quicksort. It presets the stack of working pointers to binary zero bits. Then, one set of working pointers is initialized, with the FURST pointer set to point to the first element in the data to be sorted and LAAST set to point to the last. Setting the HOW-RETURN switch to 1 indicates that this is a new iteration of the Quicksort code and processing should begin at the beginning. The SESSION-INDEX is set to 1 (this will be the first session) and the data is loaded onto the stack.

Each iteration of the code in Listing Three first pulls data from the stack and then puts it into the WORKING-INDEXES. The value of the SESSION-INDEX determines which data is pulled. By controlling the values for the SESSION-INDEX and the HOW-RETURN switch, you control how each program loop functions.

The program logic in Listing Four examines a specific group of table elements. Even though the members under consideration change continually, the examination process is exactly the same; hence the application of recursive processing.

The program logic establishes the first element to be a pivot point around which other comparisons will be made. Elements are examined from left to right, and from right to left, and element swaps are made where indicated. The end result is that the pivot element has been relocated and now divides the group into two smaller groups, where all elements to the left of the pivot are smaller than the pivot, and all elements to the right are larger. This produces two new, smaller groups that are then examined in the same manner.

Listing Five prepares the Quicksort environment to examine first the left side, and then the right side of the two newly created strings of data to be sorted. When the index values have been set, the program simply calls Quicksort again. After Quicksort examines both strings and returns control to this iteration of the code, the program tests to see if this iteration is the first one that initiated the sort. If that is the case, the sort is complete. If not, the pointer to session data is reduced by one and, in effect, when Quicksort is called again (see Listing Six), control is returned to the prior program iteration.

What is the difference between a typical user sort, where every element is compared against every other element, and a recursive Quicksort? In large volume sorting operations, the differences are impressive. Recursive Quicksort could mean saving minutes or even hours when sorting large amounts of data. The recursive process is very powerful and has many uses in mathematical analysis. Quicksort is only one application of this type of programming logic.

Conclusion

While this example illustrates the use of a simulated recursion Quicksort in Cobol, this process can be used in many other types of languages including C and Pascal. The use of the recursive Quicksort can greatly reduce the time needed to sort large amounts of data, which can be useful regardless of the programming language.

DDJ

Listing One

 01  TABLE-TO-BE-SORTED.
     02 TABLE-ENTRY   PIC X(100) OCCURS 32000 TIMES.
*
 01  SWAP-ELEMENT     PIC X(100).
 01  PIVOT-VALUE      PIC X(100).
*
 01  WORKING-INDEXES.
     02 FURST         PIC 9(5) USAGE BINARY.
     02 LAAST         PIC 9(5) USAGE BINARY.
     02 PIVOT         PIC 9(5) USAGE BINARY.
     02 HOW-RETURN    PIC 9(5) USAGE BINARY.
*
 01  TABLE-OF-INDEXES.
     02 CURRENT-INDEXES OCCURS 100 TIMES.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
 01  SESSION-INDEX    PIC 9(5) USAGE BINARY.
*
 01  LEFT-INDEX       PIC 9(5) USAGE BINARY.
 01  RIGHT-INDEX      PIC 9(5) USAGE BINARY.

Back to Article

Listing Two

 INITIALIZE-SORT.

     MOVE LOW-VALUES TO TABLE-OF-INDEXES.
     MOVE 1 TO FURST
               HOW-RETURN
               SESSION-INDEX.
     MOVE 32000 TO LAAST.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).

Back to Article

Listing Three

CALL-QUICKSORT.
     MOVE CURRENT-INDEXES (SESSION-INDEX) TO
         WORKING-INDEXES.
     IF HOW-RETURN = 2 GO TO DO-PIVOT-TO-LAST.
     IF HOW-RETURN = 3 GO TO SEE-IF-WE-ARE-ALL-DONE.
     IF FURST NOT < LAAST GO TO SEE-IF-WE-ARE-ALL-DONE.

Back to Article

Listing Four

 SPLIT-THE-LIST.
     MOVE TABLE-ENTRY (FURST) TO PIVOT-VALUE.
     MOVE FURST TO LEFT-INDEX.
     COMPUTE RIGHT-INDEX = LAAST + 1.
     PERFORM WITH TEST AFTER UNTIL
             RIGHT-INDEX <= LEFT-INDEX
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (LEFT-INDEX) >= PIVOT-VALUE
             ADD 1 TO LEFT-INDEX
         END-PERFORM
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (RIGHT-INDEX) <= PIVOT-VALUE
             SUBTRACT 1 FROM RIGHT-INDEX
         END-PERFORM
         IF LEFT-INDEX < RIGHT-INDEX
             PERFORM EXCHANGE-TWO-ELEMENTS
         END-IF
     END-PERFORM.
     MOVE FURST TO LEFT-INDEX.
 EXCHANGE-TWO-ELEMENTS.
     MOVE TABLE-ENTRY (LEFT-INDEX) TO ENTRY-HOLDER.
     MOVE TABLE-ENTRY (RIGHT-INDEX) TO
          TABLE-ENTRY (LEFT-INDEX).
     MOVE ENTRY-HOLDER TO TABLE-ENTRY (RIGHT-INDEX).
 EXCHANGE-TWO-ELEMENTS-EXIT.
     MOVE RIGHT-INDEX TO PIVOT.


Listing Five

 DO-FIRST-TO-PIVOT.
     MOVE 2 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE LAAST = PIVOT - 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.

*
 DO-PIVOT-TO-LAST.
     MOVE 3 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE FURST = PIVOT + 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.


Listing Six

*
 SEE-IF-WE-ARE-ALL-DONE.
     SUBTRACT 1 FROM SESSION-INDEX.
     IF SESSION-INDEX > 0
         GO TO CALL-QUICKSORT.
     STOP RUN.