Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Softpanorama DOS History Page

Introduction

I am writing this page about semi-forgotten but very influential epoch in programming. There have always been a gifted young programmers, and there always will be. But PC revolution was a unique period that probably will never be repeated. It the real revolution in programming despite the fact that DOS was a pretty primitive OS, actually a program loader and a couple of dozens of utilities. PC was the first computer that gave programmer unlimited time to develop their own programs but also with large scale social activities around it in the form of PC user groups. And at the beginning the field was quite open for anybody with talent to make his/her mark: it was era of re-invention of old concepts on a new level and creation of new one.  Companies like Borland and Lotus were created in garages before they became large players.

DOS (Disk Operating System) was a derivative of  CP/M. The latter was  a single-user, single-tasking computer operating system that uses a command-line interface. It was written by Gary Kildall, the brilliant programmer who single-handily introduced several important concepts into microcomputer OS design: usage of BIOS is probably the most important one. CP/M dominated the world of 8-bit microprocessors.

Here how Wikipedia cover this development:

Tim Paterson was 24 when he wrote DOS and just out of the college. Here how he recollects the events in his blog entry The First DOS Machine

Seattle Computer Products (SCP) introduced their 8086 16-bit computer system in October 1979, nearly two years before the introduction of the IBM PC. By "computer system", I actually mean a set of three plug-in cards for the S-100 bus: the 8086 CPU card, the CPU Support Card, and the 8/16 RAM. At that time SCP did not manufacture the S-100 chassis these cards would plug into. That chassis and a computer terminal would be needed to make a complete working computer.

The S-100 Bus

Inside of a modern personal computer you'll find a motherboard crammed with the heart of the computer system: CPU, memory, disk interface, network interface, USB interface, etc. Off in one corner you usually find four or five PCI slots for add-in cards, but for most people no additional cards are needed (except maybe a graphics card).
 

In contrast, the S-100 Bus motherboard contained no components at all. A full-size motherboard had nothing but 18 – 22 card slots. Each slot accepted a 5" x 10" S-100 card with its 100-pin edge connector. A typical computer system would have a card with a CPU, possibly several cards with memory, a card for a floppy disk interface, a card for serial I/O, possibly a video card, etc.
 

This arrangement was started by MITS with the Altair 8800 computer, but eventually became standardized by the Institute of Electrical and Electronics Engineers as IEEE-696. During the standardization process, the S-100 bus was extended from being an 8-bit bus (typically used by 8080 and Z80 processors) to a 16-bit bus. It was this extension to 16-bits that made the S-100 bus a suitable target for the 8086 computer from SCP.
 

SCP also wanted to take advantage of the vast range of existing cards for the S-100 bus. They didn't need to make cards for disk interface, serial I/O, video, etc. since they were already available. Even the (empty) chassis itself was a standard item. An existing computer owner could simply swap out his 8-bit CPU card and replace it with the 16-bit SCP card, and all the hardware would work together (but the software was another matter).

The SCP 16-bit Computer System

The 8086 CPU card was an Intel 8086 microprocessor with dozens of logic chips needed to interface it to the S-100 bus. The signals and timings of the bus were built around the original 8-bit Intel 8080, and it took a lot of "glue" logic to create the same signals with a different microprocessor (this was also true for the Z80). For the 8086, however, there was also a significant added layer of working in "8-bit mode" or "16-bit mode". These modes were defined by the IEEE standard so that a 16-bit CPU could be used with existing 8-bit memory with a performance penalty, or with new 16-bit memory at full speed. Essentially, the CPU card could request 16 bits for each memory access. If there was no response, the card went into 8-bit mode: the microprocessor would be stopped momentarily while logic on the card ran two consecutive 8-bit memory cycles to fetch the required 16 bits.
 

The SCP 8086 CPU had a mechanical switch on it that allowed the microprocessor to run at either 4 MHz or 8 MHz (while a processor you get today would run at around 3,000 MHz = 3 GHz). When SCP first started sales, Intel could not yet provide the 8 MHz CPU chip so early units could only be run at 4 MHz.
 

The CPU Support Card was a collection of stuff needed to make a working computer. The most important items were:

• A boot ROM with debugger.
   
• A serial port to connect to a computer terminal.
   
• A time-of-day clock.

The 8/16 RAM had 16 KB (not MB!) of memory. It could operate in "16-bit mode" so the 16-bit processor could run at full speed. In the early days, using four of these cards to build a system with 64 KB of memory would have been considered plenty.
 

The only 16-bit software available when the system was first released was Microsoft Stand-Alone Disk BASIC. SCP did not make a floppy disk controller, but supported disk controllers made by Cromemco and Tarbell.

Development Timeline

I earned my BS in Computer Science in June of 1978 and started work at SCP. Intel just announced their new 8086 microprocessor, and I was sent to a technical seminar to check it out. The May 1978 issue of IEEE Computer Magazine had published the first draft of the S-100 standard which included 16-bit extensions, so I was excited about the possibility of making a 16-bit S-100 computer. My primary duties at SCP were to improve and create new S-100 memory cards, which at that time were SCP's only products. But I was given the go-ahead to investigate a computer design when I had the time.

By January of 1979 my design for the 8086 CPU and CPU Support Card had been realized in prototypes. I was able to do some testing, but then hardware development needed to be put on hold while I wrote some software. Not even Intel could provide me with an 8086 assembler to do the most basic programming, so I wrote one myself. It was actually a Z80 program that ran under CP/M, but it generated 8086 code. Next I wrote a debugger that would fit into the 2 KB ROM on the CPU Support Card.

In May we began work with Microsoft to get their BASIC running on our machine. I brought the computer to their offices and sat side by side with Bob O'Rear as we debugged it. I was very impressed with how quickly he got it working. They had not used a real 8086 before, but they had simulated it so BASIC was nearly ready to go when I arrived. At Microsoft's invitation, I took the 8086 computer to New York to demonstrate it at the National Computer Conference in the first week of June.

There was a small setback when the June 1979 issue of IEEE Computer Magazine came out. The draft of the IEEE S-100 standard had changed significantly. I got involved in the standards process to correct some errors that had been introduced. But I still had to make design changes to the 8086 CPU which required a whole new layout of the circuit board, with a risk of introducing new errors. It turned out, however, that no mistakes were made so production was able to start 3 months later.

Evolution

The 16 KB memory card was eventually replaced by a 64 KB card. Intel introduced the 8087 coprocessor that performed floating-point math, and SCP made an adapter that plugged into the 8086 microprocessor socket that made room for it. Later SCP updated the 8086 CPU card so it had space for the 8087.

The software situation did not change until I wrote DOS for this machine, first shipping it in August 1980.

When IBM introduced their PC in August 1981, its 8088 processor used 8-bit memory, virtually identical in performance to using 8-bit memory with the SCP 8086 CPU. Except IBM ran their processor at 4.77 MHz while the SCP machine ran at 8 MHz. So the SCP 8086 computer system was about three times faster than the IBM PC.

IBM also reintroduced memory limitations that I had specifically avoided in designing the 8086 CPU. For S-100 computers, a low-cost alternative to using a regular computer terminal was to use a video card. The video card, however, used up some of the memory address space. The boot ROM would normally use up address space as well. SCP systems were designed to be used with a terminal, and the boot ROM could be disabled after boot-up. This made the entire 1 MB of memory address space available for RAM. IBM, on the other hand, had limited the address space in their PC to 640 KB of RAM due to video and boot/BIOS ROM. This limitation has been called the "DOS 640K barrier", but it had nothing to do with DOS.

Microsoft took full advantage of the SCP system capability. In 1988, years after SCP had shut down, they were still using the SCP system for one task only it could perform ("linking the linker"). Their machine was equipped with the full 1 MB of RAM – 16 of the 64 KB cards. That machine could not be retired until 32-bit software tools were developed for Intel's 386 microprocessor.

Posted by Tim Paterson at 2:15 PM 0 comments

In July 1981, Microsoft bought all rights to the DOS from Seattle Computer, and the name MS-DOS was adopted. Shortly afterward, IBM announced the Personal Computer, using as its operating system what was essentially Seattle Computer's 86-DOS 1.14. Microsoft has been continuously improving the DOS, providing version 1.24 to IBM (as IBM's version 1.1) with MS-DOS version 1.25 as the general release to all MS-DOS customers in March 1982.  Version 2.0, released in February 1983, has just been announced with IBM's new XT computer. There was also an interesting article "the roots of DOS" in IBM Softalk magazine dated March, 1983:

One does not write an operating system and fail to pick up a little wisdom in the process, particularly when that operating system becomes the property of Microsoft Corporation.

Tim Paterson, who has changed jobs and companies fairly often in the past few years, is satisfied with his position at present. He's at Seattle Computer, a company that made its name in the S-100 market and has since developed its own microcomputer--the Gazelle. It's been almost a year since he quit Microsoft. His experiences constructing an operating system that eventually would be central to IBM's Personal Computer and many other computers is quite a story.

Seen and Not Seen. Paterson looks good. He wears faded jeans. He has a dark beard and moustache, and he often breaks into a mischievous grin. A terrific programmer and hardware engineer, at twenty-six Paterson is typically innocent-looking.

He and his kind are the backbone of computer companies. There is no shortage of business people and production people in the computer industry. There are only a few terrific programmers. Everyone else is replaceable. Yet, in a big company, programmers are sometimes the least known, least appreciated employees.

"With all the code being written out there, who gets the credit? People like Bill Gates get it all and he hasn't written anything in years," says Paterson.

Paterson has been a pawn, a very valuable pawn, in a gigantic game of corporate chess. He has been moved around the board and asked to perform numerous tasks, some of which he'd like to forget. Like any good pawn, he's been relatively straightforward and dependable. But deep down, he's always wanted to be his own master, to call his own moves.

"My dad was an electrical engineer and when I went to school it was the first thing I tried," Paterson says.

In high school, Paterson took a semester of Fortran. He worked with a 7400, one of the TTL series of small logic chips. He didn't learn good textbook design from classes. "I learned it by reading and playing with it. I got a lot of exposure to electronics stuff at home."

It was as a student at Seattle's University of Washington that Paterson first encountered personal computers. In early 1976, his roommate bought an IMSAI 8080. "He provided the cash. I selected and maintained it," recalls Paterson. "It had a 4K memory board with the 8080 chip and no I/O devices. You could play a few stupid games like 'chase the bit,' which was entertaining for fifteen minutes at a time."

Days of Wire and Solder. Later that year, Paterson got a job as a technician at a Seattle-area retail computer store. There he was an eyewitness to those early days when the only way to own a microcomputer was to buy components and assemble it yourself. He's not kidding when he says, "Life begins with a disk drive."

With his university courses and practical experience in the retail store, Paterson learned quickly. He started toying around with designing his own peripheral boards.

"I got to know Rod Brock of Seattle Computer when he came into the store periodically. We were selling his boards. Eventually he asked me to consult for Seattle Computer.

"They were having problems with a 16K static memory board for the S-100," Paterson continues. "Rod Brock hired me in June 1978, at fifty dollars a day, to make the board work. I left the retail computer store at that time." After a few weeks of consulting, he was made a salaried employee of Seattle Computer.

In his computer science classes, Paterson had become interested in operating systems, as well as hardware and compilers. After receiving his bachelor of science degree in June '78, he attended graduate courses off and on for about another year. But he gradually lost interest. "I thought they were too oriented towards theory and not what I needed."

At Seattle Computer he at first worked on several projects--redesigning an S-100 memory board, which led to two new memory board designs. Things changed when he attended a local seminar on the Intel 8086 chip in late July 1978.

"I gained the respect of Rod Brock and made suggestions. I thought doing something with the 8086 would be neat and Brock gave it the go-ahead.

"The first design of the 8086 CPU card was finished by the end of January. We had a prototype by May 1979. We built three boards, but didn't wire them all up. There were both layout and design errors, but we got two prototypes working."

Rainy Day Computer. Seattle Computer was toying with the idea of eventually building its own computer, thus the CPU card project. They wanted to diversify, but had no firm business plan.

Once a prototype of the 8086 CPU was up and running, Seattle was approached by Digital Research to see if it could get CP/M to run on it. Microsoft, which had moved to the Seattle area in January 1979, wanted to see if some of its programs would work, too. At the end of May 1979, Paterson went to Microsoft to work with Bob O'Rear there. In a week or so, Paterson cranked out all 32K of Microsoft's Basic onto the 8086.

"That's pretty remarkable," says Paterson. "Microsoft already had developed several good utilities, like a cross-assembler for use with the PDP-10. There were a few bugs, but basically the CPU worked and the development tools worked."

At the 1979 National Computer Conference in New York, Seattle Computer was the guest of Microsoft and Lifeboat. They showed off standalone Basic-86, then the only software for the 8086. Seattle Computer started shipping the product with its CPU card in November, primarily to software developers.

In April 1980, Paterson began work on an operating system.

"We needed an operating system at Seattle Computer for our own computers and I wanted to do one. So we decided to go for it.

"I was waiting for Digital to come out with CP/M-86. I thought they would have it real soon. If they had beat me I wouldn't have taken the trouble.

"I had always wanted to write my own operating system. I've always hated CP/M and thought I could do it a lot better."

Fast and Grimy. In the spring of 1980, Paterson started working on what would become MS-DOS. By July, he had finished roughly 50 percent of the operating system and called it QDOS 0.10 (for quick and dirty). He quickly found a bug and it became QDOS 0.11.

"Step one was to write down what CP/M-80 did. Step two was to design a file system that was fast and efficient."

One of the significant differences between MS-DOS and CP/M-86, when it finally appeared, was the file management system. CP/M usually provides a window to no more than 16K or 32K. With MS-DOS, the entire file is available. Paterson created QDOS's file management module using the same method found in standalone Basic-86.

"I'm into bottom-up programming. You know that you're going to need certain functions later in the program. I build tools on which to make the next layer.

"When you're programming top-down, it's stepwise refining going from general actions to smaller actions. With my method there isn't a lot of diagramming. Bottom-up programming is definitely legitimate, it just doesn't get a lot of press."

By the end of August 1980, QDOS 0.11 worked well and was being shipped. It didn't stay QDOS very long, and not many copies were distributed. For the much improved update, Paterson worked hard to include all the necessary features of a complete operating system.

"There was an assembler, resident in the operating system, and debugging, but no editor. I wrote the quickest line editor I could imagine--quick in how fast I wrote it, two weeks.

"I was aghast," says Paterson, "when I heard that IBM was using it and not throwing it out the window."

Eighty-six on Cue. In December 1980, Paterson and company came out with 86-DOS, 0.33, which had significant improvements over QDOS. "86-DOS reflected pretty much everything we had learned so far. Just about the only thing it didn't have was variable sector record sizes. The assembler, originally written on the Z-80, was made faster. We also made some changes in the system calls. It was a pretty polished package when it was released."

Starting at the end of 1980, Seattle Computer sold 86-DOS to OEMs (original equipment manufacturers) and other companies like Microsoft.

"They [Microsoft] paid us a flat fee. It was not a per-copy royalty, but per OEM. Part of the contract said we couldn't ask them who they were selling it to or planning to sell it to."

In early 1981 the IBM Personal Computer had not yet been announced, but rumors were flying about Big Blue's micro. "We all had our suspicions that it was IBM that Microsoft was dealing with, but we didn't know for sure."

Around April 1981, while he was doing some internal changes on 86-DOS--modifying system calls and including error handling for hard disks--Paterson decided to quit Seattle Computer. In May, he went to Microsoft to work full-time on the PC-DOS version of 86-DOS.

"The first day on the job I walk through the door and 'Hey! It's IBM,' " says Paterson, grinning impishly. "I worked at Microsoft a neat eleven months. In May, June, and July I worked on things I hadn't quite finished, refining PC-DOS."

International Business Machinations. This was the beginning of an eleven-month hurricane. Almost daily, Paterson shipped stuff to Boca Raton for IBM's approval, and IBM would instantly return comments, modifications, and more problems.

"They were real thorough. I would send them a disk the same day via Delta Dash. IBM would be on the phone to me as soon as the disk arrived." Paterson pauses and winds up. He's remembering one request that clashed violently with his view of the project.

"IBM wanted CP/M prompts. It made me throw up." But when IBM asks, you comply if you're a lowly programmer, and that is what Paterson did.

He finished PC-DOS in July, one month before the pc was officially announced to the world. By this time, 86-DOS had become MS-DOS.

"Microsoft wanted to own it--pay all monies now and take it off Seattle Computer's hands. Both companies realized a good deal when they saw it. Seattle Computer really didn't have the marketing clout of Microsoft.

"So on July 27, 1981, the operating system became Microsoft's property. According to the deal, Seattle Computer can still see the source code, but is otherwise just another licensee. I think both companies were real happy. The deal was closed just a few weeks before the pc was announced. Microsoft was quite confident." Paterson pauses.

"Selling it was the right move. Seattle Computer is doing good without it. The timing was appropriate. I was invited to sit in on the meeting between Rod Brock and Paul Allen. I was flattered."

Is There Life after DOS? After the initial version of PC-DOS, Paterson went on to other programming tasks at Microsoft. He worked on an 8086 version of Microsoft's Basic compiler.

Paterson is like many programmers in the industry. Sure, he likes elegance. Sure, he likes simplicity. Sure, he likes to make things easy for the user. But what he likes more than anything else in a program or system is speed.

"I love assembly language. I'm a speed freak, especially with mathematical routines. If there's a loop that you want to repeat five times, I'll just rewrite the line that many times. Bam, bam, bam, woosh! The 8086 does normal loops real slow."

Paterson, still with Microsoft, did some consulting for Seattle Computer that fall, working on a RAM card for the IBM pc. Soon after he finished, he heard that Microsoft was working on a similar project.

"It was a real thrill to design a card for my employer's competitors. Microsoft was not too upset. They didn't chop my fingers off. By March 1982, Seattle's board had become quite popular. It came out months before anyone else came out with a multifunction board."

Late in 1981, Paterson and Microsoft got the word that IBM was looking for a 1.1 update. In November, he was made technical product manager of MS-DOS. He and his group delivered the initial version of 1.1 at the end of the year, a few days early. Then the Boca Raton deluge came.

"The whole process drove me crazy. A lot of bugs--PTRs [program trouble reports] -- kept dribbling in and IBM would make a phone call a day. It really drove me nuts. I felt like a puppet on an IBM string."

In March 1982, after two months of going back and forth with Paterson, IBM accepted 1.1. Paterson spent the last weeks of that month planning 2.0. Then, on April 1, he suddenly quit Microsoft. (Mark Zbikowski became the group manager and has brought MS-DOS to the brink of releasing the 2.0 version, which Paterson had little to do with.)

Not a man to burn his bridges, Paterson left Microsoft on good terms and returned to Seattle Computer to work, at first, on Seattle's floppy disk controller.

Wrong-Way Paterson. Seattle Computer was doing quite well. Paterson had owned 10 percent of the company since 1979, and had been an officer and member of the board. Achieving such a position at Microsoft was unlikely.

"It was not what was wrong with Microsoft, but what Seattle Computer had to offer. At Seattle, I'm director of engineering. Hey! That's really motivating. It was the basis for my moving back. I was a little irritated with Microsoft, mainly having to work with IBM. Microsoft recognizes talent. If somebody complains, they try to move them around."

Paterson moved himself, though, out the front door.

At present, he and Seattle Computer are "catching up." They have new S-100 products in the works and will have "new IBM stuff" soon.

"We're working on our expansion cards, making them with four functions instead of just two. We want to catch up with those four function guys. We're also working on a new enclosure for the Gazelle.

"I have the urge to do another operating system--to see if, under the circumstances, I couldn't do it better. I don't think I will, though, not at Seattle Computer. I don't have the time.

"Currently, my job does not include designing software, though I consider myself a software designer. I can picture all kinds of neat things--combined packages. Memory's cheap these days and it should be possible to have a spreadsheet, word processor, database, and more at fingertip control in one package.

"Still, the 8086/8088 looks like it for a while. It'll go through a software jump; it hasn't caught up with the Z-80 yet."

Speed Racer. When far from the world of programming and corporate politics, Paterson is something of a race-car nut. He codrives a Mazda RX-2 in pro rallies.

"The car has a roll cage and we wear helmets and all that. I have an RX-7 and, yeah, I'm kinda into cars."

Paterson is still looking for that elusive something. Independently minded, he seeks complete freedom. He doesn't want to work for someone else all his life. More properly put, he doesn't want always to be doing someone else's work.

Some year Paterson would like to start his own company. When his Seattle Computer stock is worth enough, he just may sell it and go off on his own.

"Don't worry, the boss knows. Rod Brock said to me, 'Tim, in a few years you'll go.' There is the potential that I'll go all the way with Seattle, but I just don't know. Small companies that make it either become big or become part of a big company."

For the moment, Paterson is just another brilliant programmer. He's happy, but a little sad sometimes.

"Who cares who wrote the operating system?"

We'll remember, Tim.

softalk for the IBM Personal Computer March 1983

The acronym DOS was not new even then. It had originally been used by IBM in the 1960s in the name of an operating system (i.e., DOS/360) for its System/360 line of mainframes.  This QDOS code was quickly polished up and presented to IBM for evaluation. IBM found itself left with Microsoft's offering of "Microsoft Disk Operating System 1.0". An agreement was reached between the two, and IBM agreed to accept 86-DOS as the main operating system for their new PC. Microsoft initially kept the IBM deal a secret from Seattle Computer Products. Microsoft purchased all rights to 86-DOS in July 1981, and "IBM Personal Computer DOS 1.0" was ready for the introduction of the IBM PC in October 1981. IBM subjected the operating system to an extensive quality-assurance program, reportedly found well over 300 bugs, and decided to rewrite the programs. This is why PC-DOS is copyrighted by both IBM and Microsoft. And in what was to become another extremely fortuitous move, Bill Gates persuaded IBM to let his company retain marketing rights for the operating system separately from the IBM PC project. So there was two version of the same OS on the market: PC-DOS (the IBM version) and MS-DOS (the Microsoft version). The two versions were initially nearly identical, but they eventually diverged.

Digital Research wanted $495 for CP/M-86 (considering PC-DOS was $40) and many software developers found it easier to port existing CP/M software to DOS than to the new version of CP/M. Since IBM's $39.95 DOS was far cheaper than anyone else's alternative everyone bought DOS.  Formally the IBM PC shipped without an operating system.  IBM didn't start bundling DOS until the second generation AT/339 came out.

Until its acquisition of QDOS and development of MS DOS of its base Microsoft had been mainly a vendor of computer programming languages. It stated with BASIC interpreter: Gates and co-founder Paul Allen had written Microsoft BASIC and were selling it on disks and tape mostly to PC hobbyists.  Later they added several other languages.  But due to the tremendous success of MS DOS Microsoft became the operating systems company. As PC became the most popular personal computer, revenue from its sales fueled Microsoft's phenomenal growth, and MS-DOS was the key to company's rapid emergence as the dominant firm in the software industry. This product continued to be the largest single contributor to Microsoft's income well after it had become more famous for Windows. 

The original version of DOS (version 1.0) was released in 1981 and quickly superseded by newer versions due to phenomenal speed of development by Microsoft. For several years they produced a new version each year and each version contained significant enhancements: 

• Version 1.25, released in 1982, added support for double-sided disks, thereby eliminating the need to manually turn the disks over to access the reverse side.
• Version 2.0, released the next year, added support for directories, for IBM's then huge 10MB hard disk and for 360KB, 5.25-inch floppy disks. This was followed by version 2.11 later in the same year, which added support for foreign and extended characters.
• Version 3.0, launched in 1984, added support for 1.2MB floppy disks and 32MB hard disks. This was soon followed by version 3.1, which added support for networks.
• DOS 3.2 was probably the most popular DOS before DOS 5 was released. It was so tiny, in fact, that it can fit on a single 360K floppy disk and still leave sufficient room on the same disk for Borland C compiler and data files.

Additions and improvements in subsequent versions included support for multiple hard disk partitions, for disk compression and for larger partitions as well as an improved disk checking program, improved memory management, a disk defragmenter and an improved text editor.

In spite of its very small size and relative simplicity, it is one of the most successful operating systems that has been developed.  Paradoxically this simple system was more popular then all versions of Unix combined despite the fact that Unix is much more complex and richer OS or may be because of that.  Due to mass market created by DOS and PCs the quality of DOS applications was very high and in most cases they simply wiped the floor of their Unix counterparts. DOS has more then a dozen variant with three main: MS DOS (Microsoft), PC DOS (IBM) and DR DOS (Digital Research, the authors of DR-DOS).

DOS is a text-based 16-Bit single-user, single-tasking operating system. The early success of Microsoft is mainly based on the success of MS-DOS.  Later versions of MS-DOS brought some changes in memory handling and peripheral support, but because of its architecture, DOS was unable to make use of the capabilities of 386 and later Intel chips. 

Though limited to a single program mode, DOS is still preferred by many programmers (mainly developers of games), because the application has full control over all resources in the PC.  Some unique programs like 1-2-3, MS Word, Norton Commander,  Xtree,  Ghost, originated in DOS. While two-button mouse was widely available approximately from 1986,  DOS programs widely used "letter accelerators" for menus. 

DOS games became the most successful software industry and many of DOS games came instant classics.  Many site on Internet still make them available for download.  Such games as Tetris, Digger, Alleycat, Frogger, Adventure of Captain Comic, Battle Chess, Lemmings, Prince of Persia, Doom  became part of software game history.

They are still often absent in Apple and Unix based applications.

DOS history outline

• 1973 Gary Kildall writes a simple operating system in his PL/M language. He calls it CP/M (Control Program/Monitor). (Control Program for Microcomputer)
• 1979
  • February Apple Computer releases DOS 3.2.
  • July Apple Computer releases DOS 3.2.1
• 1980
  • April Tim Patterson begins writing an operating system for use with Seattle Computer Products' 8086-based computer (for the new Intel 16-bit 8086 CPU).  Seattle Computer Products decides to make their own disk operating system (DOS), due to delays by Digital Research in releasing a CP/M-86 operating system. QDOS had been developed as a clone of the CP/M eight-bit operating system in order to provide compatibility with the popular business applications of the day such as WordStar and dBase. CP/M (Control Program for Microcomputers) was written by Gary Kildall of Digital Research several years earlier and was the first operating system for microcomputers in general use.
  • August QDOS 0.10 (Quick and Dirty Operating System) is shipped by Seattle Computer Products. Paterson's DOS 1.0 was approximately 4000 lines of assembler source. Although it was completed in a mere six weeks, QDOS was sufficiently different from CP/M to be considered legal. Paterson was later hired by Microsoft.  Even though it had been created in only two man-months, the DOS worked surprisingly well.  A week later, the EDLIN line editor was created.  EDLIN was supposed to last only six months, before being replaced.
  • September Tim Patterson shows Microsoft his 86-DOS, written for the 8086 chip.
  • October Microsoft's Paul Allen contacts Seattle Computer Products' Tim Patterson, asking for the rights to sell SCP's DOS to an unnamed client (IBM).  Microsoft pays less than US$100,000 for the right.
  • December Seattle Computer Products renames QDOS to 86-DOS, releasing it as version 0.3. Microsoft then bought non-exclusive rights to market 86-DOS.
• 1981
  • February MS-DOS runs for the first time on IBM's prototype microcomputer.
  • July In July 1981, Microsoft bought all rights to the DOS from Seattle Computer, and the name MS-DOS was adopted. Shortly afterward, IBM announced the Personal Computer, using as its operating system what was essentially Seattle Computer's 86-DOS 1.14. Microsoft has been continuously improving the DOS, providing version 1.24 to IBM (as IBM's version 1.1) with MS-DOS version 1.25 as the general release to all MS-DOS customers in March 1982. Now version 2.0, released in February 1983, has just been announced with IBM's new XT computer.
  • August IBM announces the IBM 5150 PC Personal Computer, featuring a 4.77-MHz Intel 8088 CPU, 64KB RAM, 40KB ROM, one 5.25-inch floppy drive, and PC-DOS 1.0 (Microsoft's MS-DOS), for US$3000. While architecturally it was largely an improved version of QDOS, IBM subjected the operating system to an extensive quality-assurance program, reportedly found well over 300 bugs, and decided to rewrite some programs. This is why PC-DOS is copyrighted by both IBM and Microsoft.
• 1982
  • May Microsoft releases MS-DOS 1.1 to IBM, for the IBM PC.  It supports 320KB double-sided floppy disk drives. Microsoft also releases MS-DOS 1.25, similar to 1.1 but for IBM-compatible computers.
• 1983
  • March MS-DOS 2.0 for PCs is announced. It was rewritten from scratch, supporting 10 MB hard drives, a tree-structured file system, and 360 KB floppy disks. October
    IBM introduces PC-DOS 2.1 with the IBM PCjr.
• 1984
  • March Microsoft releases MS-DOS 2.1 for the IBM PCjr. Microsoft releases MS-DOS 2.11.  It includes enhancements to better allow conversion into different languages and date formats.
  • August Microsoft releases MS-DOS 3.0 for PCs. It adds support for 1.2 MB floppy disks, and bigger (than 10 MB) hard disks.
  • November Microsoft releases MS-DOS 3.1. It adds support for Microsoft networks.
• 1986
  • January Microsoft releases MS-DOS 3.2. It adds support for 3.5-inch 720 KB floppy disk drives. Microsoft releases MS-DOS 3.25.
  • John Socha released Norton Commander 1.0
• 1987
  • April IBM announces DOS 3.3 for PCs, for US$120.
  • August Microsoft ships MS-DOS 3.3, the most successful version of  DOS ever.  It became de facto standard DOS in most markets quickly displacing older versions.
  • November Compaq ships MS-DOS 3.31 with support for over 32mb drives.
• 1988
  • Digital Research transforms CP/M into DR DOS.
  • June Microsoft releases MS-DOS 4.0, including a graphical/mouse interface. Dos 4.0 was not very successful.
  • July IBM ships DOS 4.0. It adds a shell menu interface and support for hard disk partitions over 32 MB.
  • November Microsoft releases MS-DOS 4.01.
• 1989
  • John Socha released Norton Commander 3.0
• 1990
  • April Microsoft introduces Russian MS-DOS 4.01 for the Soviet market. doe not have much success as DOS 3.3 was already entrenched and Pcs were weaker in comparison with Western market.
  • May Digital Research releases DR DOS 5.0.
• 1991
  • June Microsoft releases MS-DOS 5.0 which became hugely suceesfil and gradually displace Dos 3.3 as the main DOS version. It adds a full-screen editor, undelete and unformat utilities, and task swapping. GW-BASIC is replaced with Qbasic, based on Microsoft's QuickBASIC.
  • September Digital Research Inc. releases DR DOS 6.0, for US$100.
• 1993
  • March
    Microsoft introduces the MS-DOS 6.0 Upgrade, including DoubleSpace disk compression. 1 million copies of the new and upgrade versions are sold through retail channels within the first 40 days.
  • November Microsoft releases MS-DOS 6.2.
• 1994
  • February Microsoft releases MS-DOS 6.21, removing DoubleSpace disk compression due to the lawsuit.
  • April  IBM releases PC-DOS 6.3 the first version of PC DOS significantly different from MS-DOS.
  • June Microsoft releases MS-DOS 6.22, bringing back disk compression under the name DriveSpace. This became the last version of DOS for Microsoft although its popularity never reached the levels of DOS 3.3 and DOS 5.0. It was surprisingly good and feature rich version althouth IBM DOS 7 was more innovative.
• 1995
  • February IBM announces PC DOS 7, with integrated data compression from Stac Electronics (Stacker).
  • April IBM releases PC DOS 7 with REXX interpreter and xEdit style editor. Many consider this version to be an "Ultimate DOS".
  • September. Microsoft releases DOS 7 as a part of Windows 95. It provides support for long filenames when Windows is running, but removes a large number of utilities, some of which are on the Windows 95 CD in the \other\oldmsdos directory. (see http://www.nukesoft.co.uk/msdos/dosversions.shtml  )
• 1997. Version 7.1 was released by Microsoft. This version is part of OEM Service Release 2 and later of Windows 95. The main change is support for FAT 32 hard disks, a more efficient and robust way of storing data on large drives (see http://www.nukesoft.co.uk/msdos/dosversions.shtml  )

Battle between MS DOS, PC-DOS and DR-DOS

Microsoft used the loophole in IBM contact to market his own version of DOS called MS-DOS. Digital Research was the first company who tried to unseat Microsoft monopoly by producing better versions DOS then MS DOS but Microsoft proved to be a very tough competitor.  As Wikipedia stated:

The first version was released in May, 1988. Version numbers were chosen to reflect features relative to MS-DOS; the first version promoted to the public was DR-DOS 3.41, which offered comparable but better features to the massively successful MS-DOS 3.3 - and Compaq's version, Compaq DOS 3.31. (Compaq's variant was the first to introduce the system for supporting hard disk partitions of over 32MB which was later to become the standard used in MS-DOS 4.0 and all subsequent releases.)

At this time, MS-DOS was only available bundled with hardware, so DR-DOS achieved some immediate success as it was possible for consumers to buy it through normal retail channels. Also, DR-DOS was cheaper to license than MS-DOS. As a result, DRI was approached by a number of PC manufacturers who were interested in a third-party DOS, and this prompted several updates to the system.

Most significant update

The most significant was DR-DOS 5.0 in May 1990. (The company skipped version 4, avoiding comparison with MS-DOS 4.0.) This introduced ViewMAX, a GEM based GUI file management shell, and bundled disk-caching software, but more significantly, it also offered vastly improved memory management over MS-DOS. Compared to earlier MS-DOS 4.01 which already bundled a 386-mode memory manager (EMM386.SYS), capable of converting Extended Memory Specification (XMS) memory into Expanded Memory Specification (LIM 4.0 EMS) memory more commonly used by DOS applications, memory management in DR-DOS had two extra features.

First, on Intel 80286 or better microprocessors with 1MB or more RAM, the DR-DOS kernel and structures such as disk buffers could be located in the High Memory Area, the first 64KB of extended memory which were accessible in real mode due to an incomplete compatibility of the 80286 with earlier processors. This freed up the equivalent amount of critical "base" or Conventional memory, the first 640KB of the PC's RAM – which was the area in which all MS-DOS applications had to run. Using high memory was not a new idea, as this memory could previously be used by Windows applications starting with Windows/286 2.1 released in 1988, but offering more memory to old DOS applications was more interesting.

Additionally, on Intel 80386 machines, DR-DOS's EMS memory manager allowed the OS to load DOS device drivers into upper memory blocks, further freeing base memory. For more information on this, see the article on the Upper Memory Area.

DR-DOS 5 was the first DOS to integrate such functionality into the base OS (loading device drivers into upper memory blocks was possible using QEMM and MS-DOS). As such, on a 386 system, it could offer vastly more free conventional memory than any other DOS. Once drivers for a mouse, multimedia hardware and a network stack were loaded, an MS-DOS machine typically might only have 300 to 400KB of free conventional memory – too little to run most late-1980s software. DR-DOS 5, with a small amount of manual tweaking, could load all this and still keep all of its conventional memory free – allowing for some necessary DOS data structures, as much as 620KB out of the 640KB.

So much, in fact, that some programs would fail to load as they started "impossibly" low in memory – inside the first 64KB. DR-DOS 5's new LOADFIX command worked around this by leaving a small empty space at the start of the memory map.

Given the constraints of the time, this was an incredibly powerful technology which made life much easier for PC technicians of the day, and this propelled DR-DOS 5.0 to rapid and considerable popularity.

 Aggressive competition by Microsoft

Faced with substantial competition in the DOS arena, Microsoft responded strongly. They announced the development of MS-DOS 5.0 in May 1990, to be released a few months later and include similar advanced features to those of DR-DOS. This has been seen as vaporware, as MS-DOS 5.0 was released June 1991. It included matches of the DR's enhancements in memory management, but did not offer all of the improvements to the syntax of DOS commands that DR did.

DR responded with DR-DOS 6.0 in 1991. This bundled in SuperStor on-the-fly disk compression, to maximise the space available on the tiny hard disks of the time - 40MB was still not an atypical size, which with the growth of larger applications and especially Microsoft Windows was frequently not enough space. DR-DOS 6.0 also included an API for multitasking on CPUs capable of memory protection, namely the Intel 80386 and newer. The API was available only to DR-DOS aware applications, but well-behaved ordinary DOS applications could also be pre-emptively multitasked by the bundled task-switcher, TaskMax. On 286-based systems, DOS applications could be suspended to the background to allow others to run. However, DR's multitasking system was seen as technically inferior to third-party offerings such as DESQview, which could multitask applications which performed direct hardware access and graphical applications and even present them in scalable on-screen windows. Though far from being a true "multitasking" operating system, TaskMax nonetheless represented an important "tick on the box" - a feature on the list of specifications.

Microsoft responded with MS-DOS 6.0, which again matched the more important features of DR-DOS 6.0 - but the use of stolen code caused legal problems. See the article on MS-DOS for more.

Though DR-DOS was almost 100% binary compatible with applications written for MS-DOS, Microsoft nevertheless expended considerable effort in attempts to break compatibility. In one example, they inserted code into the beta version of Windows 3.1 to return a non-fatal error message if it detected a non-Microsoft DOS. With the detection code disabled (or if the user canceled the error message), Windows ran perfectly under DR-DOS. [1] This code was removed from final release of Windows 3.1 and all subsequent versions, however. (see also Embrace, extend and extinguish for other Microsoft tactics.)

IBM was the second company that tried to fight MS-DOS dominance, but it entered in the war too late when major battles were already lost. Until version 6 all versions of MS DOS and PC DOS were very similar. But at version 6 those two OSes diverged. Especially different was PC DOS 7 which many consider the best DOS ever created.  Both PC DOS 6 and PC DOS 7 arrived too late to change the history. PC-DOS 7 was substantially more reliable and easier to configure than any of its competitors. In short PC-DOS 7 was  a winner. It even contained REXX interpreter and Xedit style editor. The final release of PC-DOS was Y2K Compliant and was also known as PC DOS 2000. Versions 7 and 2000 natively support a XDF floppy format (800.com driver was used before for this purpose).

The final major version was  probably DOS 7.0, which was released in 1995 as part of Microsoft Windows 95. It featured close integration with that operating system, including support for long filenames and removal of some command line utilities, that were preserved and can installed separately from Windows 95 CDROM. It was revised in 1997 with version 7.1, which added support for the FAT32 filesystem on hard disks.

Although many of the features were copied from UNIX and CP/M, MS-DOS was a distinct OS that surpassed Unix in the command line interface sophistication. 

The Rise of the GUI

The demise of MS DOS occurred mainly due to raise of important on GUI interfaces and dramatic growth of power of personal computers. The introduction of the Apple Macintosh in 1984 brought about a surge of interest in GUIs (graphical user interfaces), and it soon became apparent that they are the future of personal computer interface.

Although many MS-DOS programs created their own sometimes very sophisticated command line based GUIs, this approach required duplication of programming effort, and the lack of a consistent GUI API made it more difficult for users to learn new programs and for developers to develop them.

It took Microsoft several years to provide high quality GUI of its own, but it finally succeeded with the  introduction of Windows 95 in 1995 which has taken market by storm making DOS obsolete. Still even previous version of Windows starting with Windows 3.0 released in 1990 used to have very capable GUI.  Protected mode and real mode are the two modes of operation supported by the Intel x86 architecture. The former enables 32-bit memory addressing, thereby permitting use of the extended memory that cannot be easily accessed from real mode. This makes it possible to assign separate memory areas to the operating system kernel and to each process (i.e., program or task), thus resulting in much more stable multitasking than can be attained with real mode.

Early versions of Microsoft Windows ran under MS-DOS, whereas later versions were launched under MS-DOS but were then extended by going into protected mode. Windows NT and its successors, Windows 2000 and XP, do not use MS-DOS; however, they contain an emulation layer on which MS-DOS programs can be operated, mainly for backward compatibility which is excellent: most DOS 1 program still can run on both Windows 2000 and XP. 

DOS Commands

MS-DOS has a relatively small number of commands, and an even smaller number of commonly used ones. Moreover, these commands are generally inflexible because, in contrast to Unix-like operating systems, they are designed to accommodate few options or arguments (i.e., values that can be passed to the commands).

Some of the most common commands are as follows (corresponding commands on Unix-like operating systems are shown in parenthesis):

CD - changes the current directory (similar to unix cd)
COPY - copies a file (cp)
DEL - deletes a file (rm)
DIR - lists directory contents (ls)
EDIT - starts an editor to create or edit text files
FORMAT - formats a disk to accept DOS files (mformat)
HELP - displays information about a command (man, info)
MKDIR - creates a new directory (mkdir)
RD - removes a directory (rmdir)
REN - renames a file (similar to unix mv)
TYPE - displays contents of a file on the screen (similar to Unix cat)

Comparison between MS-DOS and Linux

MS-DOS and Linux have much in common, primarily because MS-DOS copied many ideas from UNIX. However, there are some very fundamental differences, including:

1. Linux is a full-fledged multiuser, multitasking operating system, whereas MS-DOS is a single-user, single-tasking operating system.
2. Despite being more complex and powerful OS Linux has much weaker interface with the keyboard and the quality of full screen command mode applications is inferior to DOS.
3. MS-DOS does not have built-in security concepts such as file-ownership and permissions, which are fundamental to Linux.
4. Linux has an inverse tree-like filesystem in which all directories and files branch from a single directory, i.e., the root directory, and its subdirectories. MS-DOS can have multiple, independent root directories, such as A:, C:, D:, etc.
5. Linux uses forward slashes "/" to separate directories, whereas MS-DOS uses backslashes "\" for the same purpose.
6. Linux filenames can contain up to 255 characters. MS-DOS filenames are limited to an eight characters plus a three-character file type and have restrictions on allowable characters. Also, filenames are case-sensitive in Linux, whereas they are not in MS-DOS.
7. Linux has a richer command line utilities set than does MS-DOS, with a much greater number of commands and individual commands having greater power, flexibility and ease of use. Commands are case-sensitive in Linux, but they are not in MS-DOS.
8. Although Linux and MS-DOS both have pipes and I/O redirection, the MS-DOS pipes use a completely different -- and inferior -- implementation. 

MS-DOS Clones and Emulators

The great success of MS-DOS led to the development of several similar operating systems, including DR-DOS, FreeDOS, OpenDOS and PC-DOS. Development of FreeDOS was begun in 1994 by Jim Hall, then a physics student at the University of Wisconsin-River Falls. His motivation was Microsoft's announcement that it would stop supporting MS-DOS because of its impending replacement by Windows 95.

Like MS-DOS, FreeDOS is lean and robust, and it can run on old hardware and in embedded systems. A major improvement as compared with MS-DOS is the addition of options to the commands. FreeDOS is released under the GPL (although some software in the distribution is covered by other licenses).

Because Linux was originally developed on PCs and at a time when MS-DOS was the dominant PC operating system, a variety of tools were developed to help developers and users bridge the gap between the two operating systems. Among them is dosemu, a DOS emulator which is included with Red Hat and other distributions and on which it is possible to run DOS programs. Emulators are also available for running DOS on other versions of Unix, even on non-x86 processors.

mtools is a collection of utilities that make it easy to access an MS-DOS floppy disk from Linux by merely inserting it into the floppy disk drive and without having to use any mount commands (which can be tricky for inexperienced users). Included in mtools are more than 20 commands, all of which are identical to their MS-DOS counterparts except that the letter m is added to the start of each of their names. For example, the MS-DOS command type a:\file1.txt to display the contents of file1.txt that is located on a floppy disk would become mtype a:/file1.txt (mtools commands use forward slashes instead of backslashes).

The Future of MS DOS

Although it is widely believed that MS-DOS is an antiquated operating system with few features and capabilities, this is far from correct. In fact, although not generally publicized, MS-DOS is still used today by numerous businesses and individuals around the world. It survived for so long because is is robust, relatively simple and continue to get the job done with a minimum of maintenance.

DOS is still one of the best way to run recovery programs, low-level disk utilities,the flashing of the system BIOS and diagnostics.  In it used in several popular programs with Norton Ghost 2003 probably the most popular.

In many cases, it was not DOS itself that was the limiting factor in system performance; rather, it was the hardware, including small memories, slow CPUs and slow video cards. The capabilities of DOS have, in fact, continued to increase for several year after Microsoft Windows became widespread. This is a result of continuing advances in the hardware support and the introduction of new or improved utilities and applications. The most active segments are not MS-DOS but other DOS clones, particularly DrDos and FreeOS.  Still on PCs DOS share dramatically diminished after 1995 and is almost non-existent today, outside of some parts of Eastern Europe and Asia.

DOS will be around for many years into the future not only because of the continued existence of legacy applications and extremely rich high-quality tool chain that even today is in some segments is richer then Linux tool chain but also because of the development of new applications. The main area of growth will most likely be simple embedded applications, for which DOS is  attractive because of its extremely small size, very reliable operation, well developed toolset and zero cost (in the case of DrDos and FreeDOS).

Notes: Those pages are written by people for whom English is not a native language. Some amount of grammar and spelling errors should be expected. This is a Spartan WHYFF (We Help You For Free) site. It cannot replace the best teachers and the best books. The site contain some obsolete pages as it develops like a living tree... Some links on older pages are broken. Please try to use Google, Open directory, etc. to find a replacement link (see HOWTO search the WEB for details). We would appreciate if you can mail us a correct link. Search Amazon by keywords:     Open directory Research Index

Old News ;-)

[Jan 30, 2008] History of Data Compression in Japan

In 1987, I was asked by a magazine editor to write an article about data compression. I wrote a manuscript and an accompanying program, sent them to the editor, and forgot about them. The next time I heard from him I was told that the magazine was discontinued. So I uploaded my program, a simple implementation of the LZSS compression algorithm (see below) to PC-VAN, a big Japanese BBS run by NEC. That was May 1, 1988.

Soon a number of hobby programmers gathered and began improving on that program. The project culminated in Kazuhiko Miki's archiver LArc, which was fairly widey used in Japan. (Dr. Miki was then a medical specialist working at a governmental office. I heard he left office and began work on freeware/shareware promotion.)

The LZSS algorithm is based on a very simple idea. Suppose I'm going to write "compression" here. But probably I've already used that word before in this file. If I used that word 57 characters before, I might as well write "go 57 characters backward, and read 11 characters," or <57,11> for short. In general, when I've already used the string of characters among the recent 4096 characters, say, I encode the string by a <position,length> pair.

In Storer's [8] terminology, this is a sliding dictionary algorithm, analyzed first by Ziv and Lempel [14] and then by Storer and Szymanski [9], among others.

Later versions of my LZSS implementations and Miki's LArc used binary search trees to make string search faster; see Bell [1].

Incidentally, there are two distinct Ziv-Lempel (LZ) methods: sliding dictionary [14] and dynamic dictionary [15] in Storer's [8] terminology. The LZW algorithm [12] belongs to the latter. Most pre-LHarc compression tools, such as 'compress', 'ARC', and 'PKARC', used LZW.

During the summer of 1988, I wrote another compression program, LZARI. This program is based on the following observation: Each output of LZSS is either a single character or a <position,length> pair. A single character can be coded as an integer between 0 and 255. As for the <length> field, if the range of <length> is 2 to 257, say, it can be coded as an integer between 256 and 511. Thus, I can say that there are 512 kinds of "characters," and the "characters" 256 through 511 are accompanied by a <position> field. These 512 "characters" can be Huffman-coded, or better still, algebraically coded. The <position> field can be coded in the same manner. In LZARI I used an adaptive algebraic compression [13], [2] to encode the "characters," and static algebraic compression to encode the <position> field. (There were several versions of LZARI; some of them were slightly different from the above description.) The compression of LZARI was very tight, though rather slow.

Haruyasu Yoshizaki (Yoshi), a physician and guru hobby programmer, worked very hard to make LZARI faster. Most importantly, he replaced LZARI's algebraic compression by dynamic Huffman coding.

His program, LZHUF, was very successful. It was much faster than my LZARI. As for compression ratio, Huffman cannot beat algebraic compression, but the difference turned out to be very small.

Yoshi rewrote the compression engine of LZHUF in assembler, and added a nifty user interface. His archiver, LHarc, soon became the de facto standard among Japanese BBS users. After Prof. Kenjirou Okubo, a mathematician, introduced LHarc to the United States, it became world-famous. Other vendors began using similar techniques: sliding dictionary plus statistical compressions such as Huffman and Shannon-Fano. (I wondered why they used Shannon-Fano rather than Huffman which is guaranteed to compress tighter than Shannon-Fano. As it turned out, a then-popular book on compression published in U.S. contained a wrong description and buggy sample programs, such that Shannon-Fano outperformed (buggy) Huffman on many files.)

Although LHarc was much faster than LZARI, we weren't quite satisfied with its speed. Because LHarc was based on dynamic Huffman, it had to update Huffman tree every time it received a character. Yoshi and I tried other dynamic Huffman algorithms [5], [10], [11], but improvements were not as great as we desired.

So I took a different step: replacing LHarc's dynamic Huffman by a static Huffman method.

Traditional static Huffman coding algorithm first scans the input file to count character distribution, then builds Huffman tree and encodes the file. In my approach, the input file is read only once. It is first compressed by a sliding dictionary method like LZARI and LHarc, and at the same time the distributions of the "characters" (see above) and positions are counted. The output of this process is stored in main memory. When the buffer in memory is full (or the input is exhausted), the Huffman trees are constructed, and the half-processed content of the buffer is actually compressed and output.

In static Huffman, the Huffman tree must be stored in the compressed file. In the traditional approach this information consumes hundreds of bytes. My approach was to standardize Huffman trees so that (1) each left subtree is no deeper than its right counterpart, and (2) the leaves at the same level are sorted in ascending order. In this way the Huffman tree can be uniquely specified by the lengths of the codewords. Moreover, the resulting table is again compressed by the same Huffman algorithm.

To make the decoding program simpler, the Huffman tree is adjusted so that the codeword lengths do not exceed 16 bits. Since this adjusting is rarely needed, the algorithm is made very simple. It does not create optimal length-limited Huffman trees; see e.g. [6] for an optimal algorithm. Incidentally, my early program had a bug here, which was quickly pointed out and corrected by Yoshi.

The sliding dictionary algorithm is also improved by Yoshi using a "PATRICIA tree" data structure; see McCreight [7] and Fiala and Greene [4].

After completing my algorithm, I learned that Brent [3] also used a sliding dictionary plus Huffman coding. His method, SLH, is simple and elegant, but since it doesn't find the most recent longest match, the distribution of match position becomes flat. This makes the second-stage Huffman compression less efficient.

On the basis of these new algorithms, Yoshi began to rewrite his LHarc, but it took him so long (remember he was a busy doctor!) that I decided to write my own archiver. My archiver was quite recklessly named 'ar'. (Actually I appended version numbers as in 'ar002' for version 0.02.) I should have named it 'har' (after my name), say, because 'ar' collides with the name of UNIX's archiver. I didn't want my program to compete with LHarc, but I wanted many people to try the algorithm, so I wrote it in pure ANSI C. This is the reason 'ar' lacked many bells and whistles necessary for a real archiver.

Note: The version of 'ar002' most often found in the U.S. had a bug. Line 24 of maketbl.c should read, of course,

    while (i <= 16) {
        weight[i] = 1U << (16 - i);  i++;
    }

Somehow the bug didn't show up when compiled by Turbo C.

Yoshi finally showed us his new archiver written in C. It was tentatively named LHx. He then rewrote the main logic in assembler. Yoshi and I wrote an article describing his new archiver, which would be named LH, in the January, 1991, issue of "C Magazine" (in Japanese). The suffix 'arc' of LHarc was deliberately dropped because the people who sold ARC did not want others to use the name.

Then we learned that for the new DOS 5.0, LH meaned LoadHigh, an internal command. We decided to rename LH to LHA.

Also, I was told that the algorithm described in Fiala and Greene [4] got patented ("Textual Substitution Data Compression With Finite Length Search Windows," U.S. Patent 4,906,991, Mar. 6, 1990. Actually they got three patents! The other two were: "Start, Step, Stop Unary Encoding for Data Compression," Application Ser. No. 07/187,697, and "Search Tree Data Structure Encoding for Textual Substitution Data Compression Systems," Application Ser. No. 07/187,699.)

Furthermore, I learned that the original Ziv-Lempel compression method (Eastman et al., U.S. Patent 4,464,650, 8/1984) and the LZW method (Welch, 4,558,302, 12/1985) were patented. I also heard that Richard Stallman, of the Free Software Foundation, author of the EMACS editor and leader of the GNU project, ceased to use 'compress' program any more because its LZW algorithm got patented.

Are algorithms patentable? (See [16].) If these patents should turn out to be taken seriously, all compression programs now in use may infringe some of these patents. (Luckily, not all claims made by those algorithm patents seems to be valid.)

---

The foregoing is a slight modification of what I wrote in 1991. The year 1991 was a very busy year for me. In 1992, I joined the faculty of Matsusaka University. This opportunity should have given me more free time, but as it turned out I got ever busier. I stopped hacking on my compression algorithms; so did Yoshi.

Luckily, all good things in LHA were taken over, and all bad things abandoned, by the new great archiver zip and the compression tool gzip. I admire the efforts of Jean-loup Gailly and others.

A brief historical comment on PKZIP: At one time a programmer for PK and I were in close contact. We exchanged a lot of ideas. No wonder PKZIP and LHA are so similar.

Another historical comment: LHICE and ICE are definitely not written by Yoshi (or me or anyone I know). I think they are faked versions of LHarc.

REFERENCES

[1]

Timothy C. Bell. Better OPM/L text compression. IEEE Transactions on Communications, COM-34(12):1176--1182, 1986.

[2]

Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice Hall, 1990.

[3]

R. P. Brent. A linear algorithm for data compression. The Australian Computer Journal, 19(2):64--68, 1987.

[4]

Edward R. Fiala and Daniel H. Greene. Data compression with finite windows. Communications of the ACM, 32(4):490--505, 1989.

[5]

Donald E. Knuth. Dynamic Huffman coding. Journal of Algorithms, 6:163--180, 1985.

[6]

Lawrence L. Larmore and Daniel S. Hirschberg. A fast algorithm for optimal length-limited Huffman codes. Journal of the Association for Computing Machinery, 37(3):464--473, 1990.

[7]

Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the Association for Computing Machinery, 23(2):262--272, 1976.

[8]

James A. Storer. Data Compression: Methods and Theory. Computer Science Press, Rockville, MD., 1988.

[9]

James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. Journal of the Association for Computing Machinery, 29(4):928--951, 1982.

[10]

Jeffrey Scott Vitter. Design and analysis of dynamic Huffman codes. Journal of the Association for Computing Machinery, 34(4):825--845, 1987.

[11]

Jeffrey Scott Vitter. Algorithm 673: Dynamic Huffman coding. ACM Transactions on Mathematical Software, 15(2):158--167, 1989.

[12]

Terry A. Welch. A technique for high-performance data compression. IEEE Computer}, 17(6):8--19, 1984.

[13]

Ian H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic coding for data compression. Communications of the ACM, 30(6):520--540, 1987.

[14]

Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3):337--343, 1977.

[15]

Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, IT-24(5):530--536, 1978.

[16]

Edward N. Zalta. Are algorithms patentable? Notices of the American Mathematical Society, 35(6):796--799, 1988.

---

Haruhiko Okumura,
okumura@matsusaka-u.ac.jp

Last modified: Tue Mar 17 17:02:03 1998

[Jan 30, 2008] PkZip@Everything2.com

Oct 04 2001 |

PKZip, file compression utility

"...instrumental in inexpensive, dependable communication..." - Leonard Levine

PKZip began life humbly, as PKARC, which was effectively a clone of the ARC file compression utility. Following a legal action with SEA, ARC's developers, agreement was reached allowing one last version of the software using the old file format, and PKPAK was released to an adoring BBS public in 1986. PKWare later developed its own file format, which became immensely popular when the file format was put into the public domain, and BBS users began boycotting the ARC program and using PK programs. The BBS world began to convert all the compressed files from ARC to ZIP format, and ARC slipped into oblivion.

ARC had become popular amongst BBS users, who were paying large amounts of money to transfer files across (by today's standards) painfully slow modems. Any improvement meant money in users' pockets, and tighter compression would mean smaller files, which whipped across the POTS much faster. It's shareware status and simplicity of use were vital to the everyday user, and businesses, recognising its power and versatility began using it to archive data for better storage (necessary in the days of very expensive hard drives.

Phil Katz, the brains behind the company and the product, had already dramatically speeded up the compression process when he developed PKPAK and PKUNPAK, and now began to work on improving the compression algorithm in 1988. Phil was writing in assembly language, and used the best possible algorithms and the 386 processor's features where appropriate. He was still using the LZW algorithm, and whilst he had made improvements in compression and storage techniques, had still not 'invented' compression.

Phil's Zip algorithm was also used in gzip, and remains one of the most the most ported utilities. His improvements to the compression process, and the hatred felt by many toward the creators of ARC meant that the PKZip program had become a standard for the IBM PC under MS-DOS, and even now, remains the most popular file compression algorithm, in many Windows implementations. The MS-DOS version is now at version 2.50, and includes support for long file names.

[Dec 15, 2007] Unsung innovators David Bradley, inventor of the three-finger salute by Gina Smith

December 03, 2007 (Computerworld)

When we were doing the original IBM PC -- and consider this was a brand new hardware and software design -- it was hanging all the time," Bradley says. The only option engineers had to continue the work was to turn off the computer and start it again. That required at least a minute to boot back up because of the Power On Self Test (POST) feature that was built in. To this day, all Windows computers do a POST when they reboot; it's built into every ROM sequence.

But back in those early days, the need to reboot "would happen a lot," Bradley says. "Depending on what you were working on, that could be daily, hourly, even every five minutes if you were working on a particular shortcut."

So Bradley came up with the Ctrl-Alt-Del keystroke combination -- three keys distant enough on the keyboard to make it virtually impossible for someone to hit all three accidentally and simultaneously. "So, if you hit those keys, instead of taking a minute to start up the PC again, it would be much quicker -- the equivalent of turning the machine off and on without running POST."

The combination escaped from IBM labs and hit popular culture when application developers, in the days when programs ran on diskette, decided to publish the combination to help users start their applications faster.

After that, end users got used to it, and the rest is, well, history.

At the 20th anniversary of the unveiling of the IBM PC -- that was in August 2001 -- Bradley appeared on a panel featuring Bill Gates and other industry luminaries. "I thought we were there to have fun," Bradley says, remembering the moment that he joked with Gates about helping make his combo so well known.

Bradley laughs when recalling the joke. "I said, 'I may have invented it, but Bill [Gates] is the one who made it famous.' " In return, he received a glare from Gates.

Nowadays, Microsoft Windows intercepts the Control-Alt-Delete key combination and displays a pop-up window that allows users to shut down the PC or shows what programs are running.

Bradley muses that it's funny "that I got famous for this, when I did so many other nifty and difficult things." Among the Purdue Ph.D.'s accomplishments: He developed the ROM BIOS for the first IBM PC, led the development of the ROM BIOS and system diagnostics on the PC/XT, and was project manager for several PS/2 models. In 1992, he began working on higher-performing IBM systems built around the PowerPC RISC CPU.

Retired from IBM since 2004, Bradley has received engineering awards and will likely be immortalized as being part of the original IBM PC team. But like it or not, his place in computer history as the father of the three-finger salute is here to stay.
 

[Dec. 8, 2007, 2007] Original DOS developer content with life as high-tech 'tinkerer' By John Letzing

Dec. 8, 2007 | MarketWatch

 

 

SAN FRANCISCO (MarketWatch) -- Among the engineers who laid the groundwork for the modern software industry, Tim Paterson didn't exactly cash in on his technical prowess like many of his extraordinarily wealthy peers.

 

 

MSFT) Chairman Bill Gates plans to step back from the company he founded in 1975, and focus more of his attention and vast fortune -- estimated at just under $60 billion, according to Forbes -- on philanthropy, funding efforts like fighting AIDS and educating impoverished children.
 

Meanwhile Paterson, the architect of the computer code that helped spawn that fortune, is busying himself with a small firm operated out of his home in Issaquah, Wash., selling modified widgets designed to improve the performance of aging digital-video recorders.
 

Paterson developed the DOS operating system in 1980, the year before it was sold to Microsoft for $50,000. DOS then formed the core of what became Microsoft's Windows software, a flagship product that has stoked the Redmond, Wash.-based company's colossal fortunes over the past quarter of a century.
 

'I don't remember ever thinking at one point how big [DOS] is going to be in the future.'

For Microsoft's first fiscal quarter ended in September, the unit that includes Windows contributed $4.1 billion in sales.
 

Paterson Technology, which Paterson founded in 1989 as a diversion, will exceed $50,000 in sales this year, he said -- the same amount that DOS fetched some 26 years ago. But more importantly, he added, the firm satisfies his undying need to tinker.
 

Job at Microsoft
 

Paterson had developed DOS while working at Seattle Computer Products, and took a job with Microsoft around the time it bought the operating system, helping "tune and spruce" what became known as "MS-DOS" in its first iterations, he said. Paterson would work sporadically for Microsoft for the next 17 years on various products.

But DOS, and what it wrought, is his most prominent legacy. "I don't remember ever thinking at one point how big this is going to be in the future," Paterson said this week.
 

By the early 1990s, however, Paterson recalls thinking: "Wow, there're 100 million copies of this thing out there, and I wrote it originally."
 

Al Gillen, an analyst with IDC, said that the operating system proved historic. "DOS is fundamentally the product that made Microsoft into the powerhouse it is today," he commented.
 

The imprint of DOS on Windows lasted until the XP version, released in 2001, according to Directions on Microsoft analyst Michael Cherry. Cherry said that DOS also begat companions to Windows -- Microsoft's Office applications for word processing and other tasks. The suite is part of a unit that also contributed $4.1 billion in sales in Microsoft's September quarter. Office emerged, Cherry added, simply because the advent of computers with an operating system meant "people needed something to do with them."
 

Paterson's focus, though, has shifted away from PC software. Paterson Technology began churning out devices in 2004 that let digital-video recorders, such as discontinued lines made by ReplayTV, to continue to automatically change the channels on satellite-TV receivers.
 

Running the firm out of his house, Paterson said that he's enamored with improving such widespread, existing technologies. He is in the middle of a production run of 400 of his "translators" for digital-video recorders, and reports to be pleased with the consistent demand for them.
 

"I've always enjoyed making little gizmos," he said.
 

'He knew my name'

Paterson said that he first met Gates and Microsoft co-founder Paul Allen in 1979.

Allen, who proved to be Paterson's primary contact at Microsoft, resigned from his executive role at the company in 1983, and has since become the owner of professional sports teams, among other high-profile pursuits. Allen usually ranks highly on the annual Forbes list of the world's richest people -- with Gates typically at the top.

Paterson describes his relationship with Gates during his Microsoft days as mostly unaffected by his creation of DOS. "I was just another developer," commented Paterson.
 

"If we ran into each other at an event, he knew my name," he said, "because of the really early days when we had had some one-on-one time."
 

Later, Paterson's only contact with Gates occurred during the regular product presentations to the chief executive, something required of all Microsoft units. Gates transitioned from Microsoft's chief to the role of chairman in 2000.
 

This summer, Gates plans to dramatically reduce the time he spends at Microsoft to one day per week. The rest of his time will be dedicated to the Bill & Melinda Gates Foundation, the charitable organization he founded with his wife in 2000.
 

Paterson said that Gates has had a unique impact on Microsoft as a technologically adept executive able to see the big picture for the company's business direction.
 

"He had this impact as far as the overall vision; he knew what the other products were doing, and he had this vision of where things should go," he added. "It seemed funny to me that any old product, it still got a review by the top guy."
 

A Microsoft spokesman said that such reviews will necessarily have to be limited as Gates steps back. "It might not be the same quantity; it'll be a little more focused in specific areas that he decides upon," the spokesman commented.
 

Following the launch of his own business in the mid-1980s, Paterson rejoined Microsoft from 1986 through 1988. He left and then signed on again in 1990 to focus on the company's Visual Basic programming language. "I'd gotten married and needed to make more money," he said.
 

Upon rejoining Microsoft, Paterson said he was shown that had he stayed on with the company after his initial hiring in the early 1980s, his stock options would already have made him a millionaire.
 

"I had no idea what options really meant. It was hard to fathom," Paterson said. By the time he left Microsoft for good in 1998, however, he noted that his compensation package was "enough to retire and fix me for life."

'Just another tech company'
 

In "Pirates of Silicon Valley," a 1999 film about the origins of Microsoft and rival Apple Inc. an actor playing Paul Allen approaches a young man named Rod Brock at Seattle Computer Products and offers to buy DOS.

"Why?" a befuddled Brock responds. When Allen offers him $50,000 for it, Brock, wide-eyed, has to take a moment to catch his breath.
 

The real-life Brock, Paterson said, was a "middle-aged, balding guy" who owned Seattle Computer at that time, Paterson said, pointing out that portraying the deal as poorly considered wasn't quite accurate.
 

"Seattle Computer was really small, and it was a hardware company," Paterson elaborated. Such flat-fee arrangements were common then, he said, and it was Microsoft's additional engineering strength that ultimately made the product so valuable.
 

More irritating, Paterson said, is the lingering notion that he lifted much of DOS from an existing operating system called CP/M. That notion apparently was reinforced in a 2004 book by Sir Harold Evans, called "They Made America."
 

Paterson filed a defamation suit against Evans and his publisher in 2005. But a judge dismissed Paterson's suit earlier this year, citing that questions relating to DOS and CP/M had been widespread before the book.

According to Paterson, he had discussed making clarifications with Evans, but those talks ended when the suit was dismissed.

"He always said he wanted to get it right," Paterson said of Evans. "If he really did, he could have kept talking to me."

These days, Paterson is focused on turning out his next batch of video-recorder translators, along with developing a new model that won't require preordered parts from Taiwan.

Looking to "simplify" his life recently, Paterson shed all of his directly owned stocks, including those in Microsoft. He allows that he still likely owns some stock in the company through mutual funds, though he doesn't pay any special interest to mentions of Microsoft in the news.

"I'm coming around to reading about it as just another tech company," he said.

John Letzing is a MarketWatch reporter based in San Francisco.

DosMan Drivel The First DOS Machine

Seattle Computer Products (SCP) introduced their 8086 16-bit computer system in October 1979, nearly two years before the introduction of the IBM PC. By "computer system", I actually mean a set of three plug-in cards for the S-100 bus: the 8086 CPU card, the CPU Support Card, and the 8/16 RAM. At that time SCP did not manufacture the S-100 chassis these cards would plug into. That chassis and a computer terminal would be needed to make a complete working computer.

The S-100 Bus

Inside of a modern personal computer you'll find a motherboard crammed with the heart of the computer system: CPU, memory, disk interface, network interface, USB interface, etc. Off in one corner you usually find four or five PCI slots for add-in cards, but for most people no additional cards are needed (except maybe a graphics card).
 

In contrast, the S-100 Bus motherboard contained no components at all. A full-size motherboard had nothing but 18 – 22 card slots. Each slot accepted a 5" x 10" S-100 card with its 100-pin edge connector. A typical computer system would have a card with a CPU, possibly several cards with memory, a card for a floppy disk interface, a card for serial I/O, possibly a video card, etc.
 

This arrangement was started by MITS with the Altair 8800 computer, but eventually became standardized by the Institute of Electrical and Electronics Engineers as IEEE-696. During the standardization process, the S-100 bus was extended from being an 8-bit bus (typically used by 8080 and Z80 processors) to a 16-bit bus. It was this extension to 16-bits that made the S-100 bus a suitable target for the 8086 computer from SCP.
 

SCP also wanted to take advantage of the vast range of existing cards for the S-100 bus. They didn't need to make cards for disk interface, serial I/O, video, etc. since they were already available. Even the (empty) chassis itself was a standard item. An existing computer owner could simply swap out his 8-bit CPU card and replace it with the 16-bit SCP card, and all the hardware would work together (but the software was another matter).

The SCP 16-bit Computer System

The 8086 CPU card was an Intel 8086 microprocessor with dozens of logic chips needed to interface it to the S-100 bus. The signals and timings of the bus were built around the original 8-bit Intel 8080, and it took a lot of "glue" logic to create the same signals with a different microprocessor (this was also true for the Z80). For the 8086, however, there was also a significant added layer of working in "8-bit mode" or "16-bit mode". These modes were defined by the IEEE standard so that a 16-bit CPU could be used with existing 8-bit memory with a performance penalty, or with new 16-bit memory at full speed. Essentially, the CPU card could request 16 bits for each memory access. If there was no response, the card went into 8-bit mode: the microprocessor would be stopped momentarily while logic on the card ran two consecutive 8-bit memory cycles to fetch the required 16 bits.
 

The SCP 8086 CPU had a mechanical switch on it that allowed the microprocessor to run at either 4 MHz or 8 MHz (while a processor you get today would run at around 3,000 MHz = 3 GHz). When SCP first started sales, Intel could not yet provide the 8 MHz CPU chip so early units could only be run at 4 MHz.
 

The CPU Support Card was a collection of stuff needed to make a working computer. The most important items were:
 

• A boot ROM with debugger.
   
• A serial port to connect to a computer terminal.
   
• A time-of-day clock.

The 8/16 RAM had 16 KB (not MB!) of memory. It could operate in "16-bit mode" so the 16-bit processor could run at full speed. In the early days, using four of these cards to build a system with 64 KB of memory would have been considered plenty.
 

The only 16-bit software available when the system was first released was Microsoft Stand-Alone Disk BASIC. SCP did not make a floppy disk controller, but supported disk controllers made by Cromemco and Tarbell.

Development Timeline

I earned my BS in Computer Science in June of 1978 and started work at SCP. Intel just announced their new 8086 microprocessor, and I was sent to a technical seminar to check it out. The May 1978 issue of IEEE Computer Magazine had published the first draft of the S-100 standard which included 16-bit extensions, so I was excited about the possibility of making a 16-bit S-100 computer. My primary duties at SCP were to improve and create new S-100 memory cards, which at that time were SCP's only products. But I was given the go-ahead to investigate a computer design when I had the time.
 

By January of 1979 my design for the 8086 CPU and CPU Support Card had been realized in prototypes. I was able to do some testing, but then hardware development needed to be put on hold while I wrote some software. Not even Intel could provide me with an 8086 assembler to do the most basic programming, so I wrote one myself. It was actually a Z80 program that ran under CP/M, but it generated 8086 code. Next I wrote a debugger that would fit into the 2 KB ROM on the CPU Support Card.
 

In May we began work with Microsoft to get their BASIC running on our machine. I brought the computer to their offices and sat side by side with Bob O'Rear as we debugged it. I was very impressed with how quickly he got it working. They had not used a real 8086 before, but they had simulated it so BASIC was nearly ready to go when I arrived. At Microsoft's invitation, I took the 8086 computer to New York to demonstrate it at the National Computer Conference in the first week of June.
 

There was a small setback when the June 1979 issue of IEEE Computer Magazine came out. The draft of the IEEE S-100 standard had changed significantly. I got involved in the standards process to correct some errors that had been introduced. But I still had to make design changes to the 8086 CPU which required a whole new layout of the circuit board, with a risk of introducing new errors. It turned out, however, that no mistakes were made so production was able to start 3 months later.

Evolution

The 16 KB memory card was eventually replaced by a 64 KB card. Intel introduced the 8087 coprocessor that performed floating-point math, and SCP made an adapter that plugged into the 8086 microprocessor socket that made room for it. Later SCP updated the 8086 CPU card so it had space for the 8087.
 

The software situation did not change until I wrote DOS for this machine, first shipping it in August 1980.
 

When IBM introduced their PC in August 1981, its 8088 processor used 8-bit memory, virtually identical in performance to using 8-bit memory with the SCP 8086 CPU. Except IBM ran their processor at 4.77 MHz while the SCP machine ran at 8 MHz. So the SCP 8086 computer system was about three times faster than the IBM PC.
 

IBM also reintroduced memory limitations that I had specifically avoided in designing the 8086 CPU. For S-100 computers, a low-cost alternative to using a regular computer terminal was to use a video card. The video card, however, used up some of the memory address space. The boot ROM would normally use up address space as well. SCP systems were designed to be used with a terminal, and the boot ROM could be disabled after boot-up. This made the entire 1 MB of memory address space available for RAM. IBM, on the other hand, had limited the address space in their PC to 640 KB of RAM due to video and boot/BIOS ROM. This limitation has been called the "DOS 640K barrier", but it had nothing to do with DOS.
 

Microsoft took full advantage of the SCP system capability. In 1988, years after SCP had shut down, they were still using the SCP system for one task only it could perform ("linking the linker"). Their machine was equipped with the full 1 MB of RAM – 16 of the 64 KB cards. That machine could not be retired until 32-bit software tools were developed for Intel's 386 microprocessor.

[Sep 30, 2007] DosMan Drivel Design of DOS

I set to wo