Did Microsoft Steal Disk Compression?

Did Microsoft Steal Disk Compression?

This is Microsoft DOS 6. I love an operating system in a big box. It's the least you expect for a piece of softwarethat's so significant. But look a little closer and you'll see somethingMicrosoft wanted us to know about. Something they wanted us to see. // Thanks to SquareSpace for sponsoring this  // Yes, Microsoft were so pleased with this technology,they plonked it in a bright red star. That's right, for one reasonable price, younot only get a brand spanking new operating system, you can also conveniently double theamount of hard drive space you have! Well, I'm sold. Microsoft may have been keen to show it off,but this wasn't new technology, at least, not in the greater world of software. You see, in the first two decades of the IBMPC & compatibles, hard disk space was at a premium. In the early 80s, 10MB was a very significantamount of storage. By the early 90s, 100MB was a very significant amount

 of storage, but with the advent of Windows 3, and its multitude of applications,people were starting to cry out for more. For computers running MS-DOS, tools like PhilKat'z PKZIP was one such solution. Using it, you could compress your files intoa neat little archive. That archive could save space on your harddrive, or even be used to archive software to a single, or even multiple floppy disk. A far cheaper storage medium than hard drives. But it would be a company known as Stac Electronicswho would offer a somewhat revolutionary solution. Stac Electronics was formed in 1983, initiallyunder the extended name of 'State of the Art Consulting'. Operating initially out of Pasadena, California,the 

original 9 founders set to work as a fabless chip company with products aimed towards backupsand the tape drive industry. They quickly moved onto dedicated compressionchips and even expansion cards, that could handle file compression on the fly. Using a memory resident software driver, thesecards could seamlessly compress and decompress data creating a much higher capacity diskthan under normal conditions. By 1990, and with processor speeds increasing,the company realised that they could perform this compression/decompression completelywithin software, negating the need for expensive hardware, and released the Stacker disk compressionutility in 1991 to do just that. Sundog Software had attempted something similara few years prior, with their utility, Squish, however it was slow and awkward in use. In contrast Stacker was simple, and actuallyreduced disk access times, meaning, 

although it only needed an 8088 CPU to run, machineswith a fast enough processor would actually perform quicker than without it. Previously, in 1989, another competitor; VertisoftSystems had also released a similar product; Double Disk. However, this was a more finicky beast, whichrelied on creating virtual partitions as compressed volumes, rather than allowing you to compressyour entire hard drive in one fell swoop. The real beauty of Stacker, was that it couldalmost transparently compress an entire hard drive and you'd be none the wiser, apart fromnow having roughly double the space. By 1992, it was clear that on-the-fly compressionwas proving very appealing, and various other competition had landed, including Expanz Plusand SuperStor. But Stacker was now on version 2.0,

 and itwas even better. You see, the first version of Stacker usedsome cunning in operation; it essentially created a new drive name (D:), leaving theuncompressed host C: drive with a small amount of space to house the standard DOS boot files. After initial boot, the Stacker driver wouldthen essentially swap the drive letters over, making the compressed partition, now the C:drive. But this left some complications when applicationsmade changes to the DOS autoexec and config.sys files on the C: drive rather than the D: drive, which was actually the one used forbooting. Version 2.0 eradicated this problem by automaticallymaintaining and synchronising the boot files, and also completely hiding the uncompressedpartition. Priced at $149, Stacker 2.0 was much, muchmore affordable than buying more hard drive space. It also offered the best speed and losslesscompression ratios on the market, 

and even more importantly was reliable. Programs like Expanz were sometimes knownto cause some corruption when it failed to estimate remaining disk space effectivelyon a full drive. Stacker was therefore the obvious choice whilststill not out-pricing its competition. Between 1991 and 1992, business was lookingrosy, to the tune of approximately $44 million in sales. But Microsoft being Microsoft were havingnone of it. Wanting a piece of everything, they had decidedthat their new version of Microsoft DOS, version 6.0, should have drive compression incorporateddirectly into the OS, rather than users having to turn to these ghastly third party utilities. Naturally, their first port of call wouldbe the industry leader, Stac Electronics.... //SPON// //SPON// Now, as you might expect, Microsoft hadn'tmade this decision from a deep desire to innovate. Most of their work was built on the 

foundationsof others, and this was no different. In late 1991, Digital Research had deliveredDR-DOS 6.0, which not only included task switching ability, but thanks to a deal with AddStorIncorporated, also featured SuperStor's compression utility. Of course, DR-DOS's distribution was minutecompared to the 100 million machines MS-DOS was already installed on, but COMPUSA hadmade a deal to bundle it with all their laptops and notebooks. For Microsoft, this was an issue. The tantalising appeal of free hard drivespace, and a pseudo multi-tasking operating system might impact their market domination,and so in mid-1992, they went and sat down with Stac Electronics at their Californiaheadquarters. Now, I don't have the exact transcripts ofthat meeting, but according to various reports, including a 1993 InfoWorld article, it wentsomething like this; Hello Stac Electronics, 

we're Microsoft, we'dlike to ship Stacker with MS-DOS 6.0. -OK Sure, how much will you pay us? Nothing. But we'll give you some future licensing deals,maybe. -No. Look, give us your technology or we'll goto a competitor and leave you for dead *door slam* This is very roughly the sequence of eventsconfirmed by Stac Chairman, Gary Clow. Microsoft would later claim that they hadoffered Stac $1 million a month in licencing fees, but that Stac had demanded four timesthis amount. Regardless the meetings amounted to nothing,and so Microsoft decided to go down a different route. Enter our old friends Vertisoft, and theirdisk compression utility, DoubleDisk, which was now at version 2.5, and very firmly thebudget compression software in the market, priced at just $99.95. Being significantly on the backfoot, Vertisoftwere apparently more open to a deal with Microsoft, and the cogs were set in motion. Part of the deal Microsoft offered was thatVertisoft could have insider development access, 

enabling them to create their own suite ofcompatible programs, such as Veritisoft's Space Manager, which added a DoubleSpace Windowsinterface, along with a suite of performance utilities. In January 1992, PC Magazine described DoubleDiskas "one of those products that isn't impressive due to exceptional functionality, inspiredtechnology or a slick interface; it simply does what it promises to do", and that's allMicrosoft wanted. The hard part was out of the way, so all theyhad to do was incorporate the basic framework and algorithms into their own utility. What was this utility called, not DoubleDisk.... DoubleSpace. I tell you their marketing department wason a whole different plane of existence. By January 1993, MS-DOS 6.0 was gearing upfor it's March launch window, including the much advertised DoubleSpace. If you were a user of MS-DOS 6, you mightknow it better as DBLSPACE.EXE. When installed, the DBLSPACE.BIN kernel wouldload automatically through an undocumented pre-load API, whilst also consuming some ofyour DOS memory. But to make it fully 

suitable for the operatingsystem, Microsoft had to implement a number of changes, including making it more transparentfrom a user perspective, and to live up to it's double claims, having the ability tocompress the entire C: drive... well the first 512MB at least. Anyone who had any more than that was eithera god, or frankly, had the money to buy more hard drives. However, as soon as a beta copy of DOS arrivedin Stac Electronics offices. They knew they had to do something. Microsoft might have cut Stac out and decidedto licence technology from a competitor, but Stac had an ace up their sleeves. On the 25th January 1993, Stac entered a complaintwith the courts against Microsoft. You see, Stac Electronics had been in thegame for a long time, and had already registered a number of patents regarding their compressiontechnology. The patent they deemed Microsoft was in violationof was US # 4,701,745; the "Waterworth" patent, first registered on the 3rd March 1986, byFerranti International PLC, under direction from Stac Electronics. The patent infringement applied to the 

compressionalgorithm employed by Microsoft's, and somewhat by extension, Vertisoft's transparent procedure. In abstract terms the patent is describedas; "A data compression system includes an inputstore (1) for receiving and storing a plurality of bytes of data from an outside source. Data processing means for processing successivebytes of data from the input store includes circuit means (21-25) operable to check whethera sequence of bytes is identical with a sequence of bytes already processed, output means (27)operable to apply to a transfer medium (12) each byte of data not forming part of suchan identical sequence, and an encoder (26) responsive to the identification of such asequence to apply to the transfer means (12) an identification signal which identifiesboth the location in the input store of the previous occurrence of the sequence of bytesand the number of bytes in the sequence." It's a variation on the Lempel-Ziv compressionscheme, and what it boils down to is the use of hashing to find matches in a sliding inputwindow. Now, this is incredibly simplified, but saya file 

contained the text "The fat cat sat on the brown mat". Well, the compression algorithm file wouldscan the file, find all matching sequences, and replace them with an identifier. Like this. We've now instantly removed five bytes ofinformation. The patent describes hashing 3 bytes of dataat a time to find identical fingerprints. If you take a look at how Microsoft explainDoubleSpace compression, they talk of a similar process of finding repeated sequences, andthen encoding them as <offset,length> so subsequent matches all point back to the initial match. To save further space, the most common valuesare attributed shorter encoding than the least common. All this allows the original data to be 

restoredwithout loss. It should be noted that DoubleSpace also savedspace by reducing the cluster-overhang found within a FAT file system, but that isn't thepart in question here. It's not quite like this in reality, in realitythe hashing would calculate a fingerprint for a rolling frame of data in a 8K chunks,or 16-sector clusters, and where the fingerprints are found to be identical, those points ofdata would have the same reference. It's such a rudimentary and obvious methodof compression, used in so many compression algorithms, that it really highlights theproblems the US Patent system had in identifying what was a viable computing patent in thoseearly emerging times. There was much discussion and 

uproar aboutit during the 80s and 90s. The fact that Stac had only decided to wieldthis power now, as Microsoft threatened to crush the whole industry, is testament tothe threat they were facing. This would actually be the first patent lawsuitin Microsoft's history (although not the last), and the outcome would have significant implicationsfor both the companies involved, and how pre-existing technology ideas could be implemented goingforward. But this wasn't the only issue Microsoft hadconjured by rolling out DoubleSpace. /// By May 1993, and with litigation now in fullswing, the computing world was suddenly aware of a significant problem with Microsoft'scompression utility. InfoWorld wrote; 

"DoubleSpace uses an estimated compressionratio to estimate the free space available on a compressed drive. When DoubleSpace writes 8KB of data, it requires16 sectors of 512 bytes each, and those sectors must be contiguous. If contiguous sectors are not available, thiscauses a variety of symptoms from lost disk clusters to unreported disk corruption". Companies such as Blossom Software had evencreated utilities to check for these issues. Combined with the poor selection of DoubleSpacefocused repair utilities Microsoft included with DOS 6.0, it was evident that the OS hadbeen somewhat rushed to incorporate the functionality as soon as possible. Microsoft's answer was, in Setember 1993,to release DOS 6.2, which not only included a version bug fixed version of DoubleSpace,but also bundled a new utility called SCANDISK. Designed to replace the text based CHKDSK,Scandisk was a graphically pleasing disk repair program that importantly, could handle DoubleSpacedrive issues much better. 

The fact they were pressing forward, clearlydemonstrated the Stac lawsuit wasn't concerning them too much. But what wasn't worrying Microsoft, was definitelyworrying the third party compression companies. By this time, DOS 6 users numbered in themillions, and a reported 62% of those users were now using DoubleSpace. That's huge. What's more, you could buy the entire DOSoperating system for half the price of Stacker's software alone! The customer base for Stacker and it's peershad effectively been ripped out from under them, overnight. The only real customers left were those whowanted the best compression technology on the market, and could afford to pay for it. PC Magazines continued to tout the benefitsof Stacker over DoubleSpace but it was only a matter of time before businesses went under. The Federal court case begin in January 1994. Almost exactly a year after the original filing. 

Throughout the trial, Microsoft would putin numerous counter-claims against Stac, including that Stac was the one violating technologyMicrosoft had just acquired, that it was engaging in civil conspiracy to commit fraud and moresignificantly, that it had misappropriated a trade-secret of DOS 6.0, by making use ofthat undocumented pre-load feature in Stacker 3.1. Allegedly, this not only made the softwarecompatible with Microsoft's new operating system, but also allowed Stac to include afeature allowing users to upgrade their drive from DoubleSpace to Stacker Disk compression. Interestingly, one of the pieces of evidencesubmitted by Stac, was of Bill Gates at a DOS 6 marketing event, wearing a T-Shirt saying"We came, we saw, we doubled". This was presented to drive home how importantthe new technology was to their new OS. The proceedings rattled on for 4 weeks, butdespite the apparent 

spuriousness of the patent, it was perhaps Microsoft's aggressive dealingand litigation tactics which swayed the jury, and by the 23rd February 1994 the verdictwent in favour of Stacker Electronics with Judge Edward Rafeedie ordering Microsoft topay Stac the amount of $120,000,000 in damages, which equated to around $6 for every copyof DOS 6.x sold. However, the jury also agreed with the counterclaimthat Stac has misappropriated trade secrets, and ordered them to pay Microsoft just over£13 million in compensatory and punitive damages. Of course, it wasn't just Microsoft at faulthere, and so Vertisoft, the original infringers of the patent and who licenced their technologyto Microsoft, 

were also ordered to pay compensatory damages to Stac in the amount of $670,000,with all other claims dismissed with prejudice. Stac would immediately request a permanentcourt order blocking further sales of all DOS Operating Systems which included DoubleSpace. This led to Microsoft releasing DOS 6.21,which was identical to DOS 6.2, just without any disk compression software. People who happened to be shopping for DOSduring this period, apparently, lucked out. Although if you've still got a copy, you mighthave just lucked in! Even so, June 10th saw the Federal court rulethat 

Microsoft recall all unsold versions of DOS 6 and DOS 6.2, and prevent the saleof any new computers it had already been installed on. Of course, Microsoft now realised that itmay be in their best interests to actually work with Stac, rather than fight them, andso after temporarily getting a stay on the recall injunction, an agreement was reachedbetween the two parties, on the understanding that Microsoft would not pursue an appealwhich could be costly for everyone involved. The new deal would see Microsoft pay $1 milliona month for 43 months to licence Stac's patented technology, whilst also paying £39.9 millionfor preferred stock that could be converted in 2004 with a 15% stake for $9 a 

share. Effectively buying a significant chunk ofthe company. It also meant that Stac would not need tostump up the $13.6 million counterclaim award. Gary Clow, CEO of Stac Electronics, was quotedas saying, "Today's agreement immediately ends our conflict with Microsoft and ushersin a new era of cooperation between the two companies." Before 1994 was out, DOS 6.22 would be released. To avoid any confusion, and move on from thiswhole fiasco, it now included DriveSpace. Backwards compatible with DoubleSpace, butapparently with a slightly different compression algorithm and a great new name. It's almost like Microsoft use word laddersto choose their software names. DOS 6.22 is my favourite version of DOS, andindeed, I myself used DriveSpace on my 850MB Western Digital hard drive back in 1995, andfound it to be an uplifting and liberating experience. It's good that we got there in the end. // During this entire period, both Microsoft'sand Stac's shares had both fallen and risen, but 

understandably Stac's fluctuations weremuch more sweeping. Directly after their court win, Stac sharesjumped over $2 to $6.50 a share, with Microsoft's falling just over a dollar to $79.875. However, Stac's share price situation actuallyled to another lawsuit for the company, this time brought forward by it's shareholders. They alleged that following excellent salesduring the previous year, Stac had gone public in May 1992 at $12 per share, but had doneso knowingly just before Microsoft announced they were incorporating DoubleSpace into theirOperating System. Initially shares had surged to $15, but quicklydropped with Microsoft's announcement and Stac's subsequent loss of value. By the end of 1994, the Stac electronics compressiontechnology was actually accepted as a formal lossless 

compression standard by ANSI. Known as Lempel-Ziv-Stac, it combined thesliding window repeated data approach with Huffman coding, which breaks down longer stringsinto a series of nodes on a binary tree. It would later be used as a network compressionalgorithm under a spin-off company of Stac, known as Hifn. As for Stac. Well, by 1996 they had won and survived theirshareholder lawsuit, and 

would ultimately continue with their original semiconductorbusiness until 2002 when Stac's remaining technology assets were sold to the Symantecsubsidiary, Altiris. Of note is that Stac would make the impressiveeffort to return it's remaining cash to shareholders before dissolving. Not something you see a lot of companies doingbefore they disappear, and perhaps a morally astute nod to their earlier disagreements. The mammoth Microsoft, of course, is stillwith us, and would solider on with DriveSpace throughout Windows 95 and onwards. In fact, the remnants of it are still shippedin 

Windows 10, albeit in a reduced form and with much less fanfare. We came, we saw, we doubled. Man, it's those limitations which really madethose decades such an exciting time. Thanks for watching. Have a great evening.