STAC ELECTRONICS FILES PATENT INFRINGEMENT SUIT AGAINST MICROSOFT The following is the text of Stac Electronics' patent infringement complaint against Microsoft Corp.: IRELL & MANELLA Morgan Chu Wayne M. Barsky Mark A. Flagel Jeffrey L. Arrington Steven S. Weiner 1800 Avenue of the Stars Los Angeles, California 90067-4276 Telephone: (310) 277-1010 SHEA & GOULD John Kidd Nicholas L. Coch 1251 Avenue of the Americas New York, New York 10020 Telephone: (212) 827-3000 Attorneys for Plaintiff Stac Electronics UNITED STATES DISTRICT COURT CENTRAL DISTRICT OF CALIFORNIA STAC ELECTRONICS, a California corporation, Plaintiff, v. MICROSOFT CORPORATION, a Delaware corporation, Defendant. Civil No. COMPLAINT FOR PATENT INFRINGEMENT DEMAND FOR JURY TRIAL Plaintiff Stac Electronics (``Stac'') demands a jury trial on all issues and alleges as follows: JURISDICTION AND VENUE 1. This is an action for patent infringement arising under the Patent Act of the United States, 35 U.S.C. 271 and 281. This Court has subject matter jurisdiction over the matters complained of under 28 U.S.C. 1338(a) and 1331. 2. Venue is proper in this judicial district pursuant to 28 U.S.C. 1400(b) and 1391(c), as defendant Microsoft Corporation (``Microsoft'') resides and has committed acts of patent infringement in this judicial district. THE PARTIES 3. Stac is a corporation organized and existing under the laws of the State of California and has its principal place of business at 5993 Avenida Encinas, Carlsbad, California 92008. Stac designs, develops, markets and supports data compression/decompression products that increase the effective capacity of computer-related storage devices and the transmission rates of data communication systems. Stac is the leading supplier of high performance data compression products for personal computers. 4. Microsoft is a corporation organized and existing under the laws of the State of Delaware. Microsoft's principal place of business is located at One Microsoft Way, Redmond, Washington 98052. Microsoft develops, produces and markets, among other things, a broad range of software for business and professional use, including operating systems, languages and applications programs. Microsoft is the world's largest software company, with reported revenues in excess of $2.7 billion in fiscal 1992, and some 12,000 employees in 27 countries. Microsoft produces and markets, among other products, the MS-DOS operating system software for IBM and IBM-compatible personal computers. FACTUAL BACKGROUND 5. An operating system is a group of programs that, among other tasks, translates user commands to the computer, schedules and implements the execution of applications programs, allocates computer memory, and manages the flow of information and communication among various components of the computer system. Application programs ``attach'' to the underlying operating system and, when called upon to do so by the operating system, perform discrete functions such as word processing, graphics and spreadsheet operations. 6. MS-DOS is currently installed on in excess of 100 million IBM and IBM-compatible personal computers, and Microsoft ships more than 20 million units of MS-DOS every year. Microsoft's MS-DOS is the predominant operating system in the IBM and IBM-compatible personal computer market. MS-DOS is marketed principally to original equipment manufacturers (OEMs) under agreements that allow the OEMs to distribute the MS-DOS operating system software with their personal computers. 7. Stac is the manufacturer and publisher of a data compression utility progrm known as STACKER, which attaches to DOS operating systems such as MS-DOS, as well as other operating systems. Utility programs are a large and diverse family of application programs that are designed to enhance personal computer performance. The principal function of STACKER is to compress data stored on the hard disk of IBM nad IBM-compatible personal computers when the data is not being used, and later decompress such data w hen it is to be used, thereby increasing the effective storage capacity of the computer. 8. Although there are a number of software companies which offer data compression programs, Stac is the acknowledged industry leader in developing and marketing data compression technology, and STACKER is currently the best-selling data compression program for use on the DOS operating system. Stac's proprietary data compression technology, developed over the course of five years and at substantial cost, is protected by a number of patents, including U.S. Patent Nos. 5,016,009 (the "009" patent) and 4,701,745 (the "745" patent) (collectively, the "patents in suit"). 9. Stac's proprietary data compression technology is relied upon daily by more than four million computer users worldwide. STACKER is the winner of PC Magazine's Technical Excellence Award, Windows Magazine's WIN 100 Award, PC Magazine's Editor's Choice Award, PC Computing's Most Valuable Product Award, Byte Magazine's Best of Comdex-Finalist Award, and National Software Testing Lab's Recommendation (Five Stars), and is the recipient of numerous additional industry accolades. 10. Largely as a result of the tremendous market acceptance of STACKER, which utilizes Stac's proprietary data compression technology, Stac quickly grew from a company with 25 employees and revenues of less than $1 million in 1989 to a company with more than 200 employees and a market capitalization in excess of $150 million today. 11. The personal computer software industry is characterized by rapid technological change which requires software developers continually to enhance existing products and develop new products. A critical factor in the success of a new or enhanced product is getting the product to market quickly in response to new user needs or technological advances, while at the same time maintaining the integrity and quality of the product. 12. It was a well-known fact in the personal computer industry as early as 1991 that Microsoft's MS-DOS 5.0 retail upgrade sales were rapidly declining with each passing quarter. As Microsoft's flagship product -- with approximately $700 million in revenue per year attributable to MS-DOS sales alone -- Microsoft was under intense market pressure to stimulate MS-DOS sales with an improved version of the MS-DOS operating system. 13. Due in part to the overwhelming market success of STACKER, the personal computer industry quickly recognized that an operating system capable of incorporating a high-quality data compression utility such as STACKER would be highly competitive. Indeed, the principal competitor of Microsoft's MS-DOS -- Novell's DR-DOS operating system -- had already incorporated a data compression utility in its operating system software. 14. Microsoft's Chairman and Chief Executive Officer, William H. Gates, became personally interested in Stac's proprietary data compression technology, and the possibility of using such technology in MS-DOS, in 1991, at approximately the same time that STACKER was receiving a number of coveted industry awards for technical excellence and overall product quality. 15. Mr. Gates met with Stac's President, Gary W. Clow, at the Fall Comdex-91 ceremony in Las Vegas. During a discussion which preceded the award ceremony, Mr. Gates said that Microsoft was considering including a data compression capability in the next release of MS-DOS. Mr. Gates further stated that Microsoft would not be developing this capability internally, but rather would seek to obtain another company's data compression technology for inclusion in MS-DOS. The Editor-in-Chief of PC Magazine, Michael J. Miller -- whose magazine would later that evening present its Technical Excellence Award to Stac -- told Mr. Gates before the ceremony began that STACKER was a first-rate product. Mr. Gates asked Mr. Clow to contact Microsoft after Mr. Clow returned to California, and Mr. Clow agreed. 16. In late 1991, as a result of Mr. Gates' interest, Mr. Brad Chase -- who was then Microsoft's Group Product Manager and who today is Microsoft's General Manager for MS-DOS -- and Mr. Clow began discussing the possibility of Microsoft licensing Stac's proprietary data compression technology for inclusion in future versions of the MS-DOS operating system. 17. During the ensuing months of negotiations, Microsoft proposed that Stac grant to Microsoft a world-wide license to incorporate STACKER data compression technology and know-how into future versions of its MS-DOS operating system software. Microsoft steadfastly refused, however, to offer to pay Stac any royalty for Stac's patented data compression technology. 18. Mr. Chase made it clear during the negotiations that Microsoft was considering including data compression capability in future versions of the MS-DOS operating system, and that if it were unable to reach an agreement with Stac, it would obtain this capability elsewhere, even though Microsoft believed -- as it told Stac on numerous occasions -- that STACKER was the best data compression product for the DOS market. When the subject of incorporating data compression technology other than Stac's arose, Mr. Clow reminded Mr. Chase and others that Stac owned patent rights to its data compression technology and would enforce its patents against any infringers. At least one draft agreement was provided to Microsoft that included a specific reference to Stac's '009 patent. 19. Microsoft attempted to persuade Stac that its proposal to incorporate Stac's proprietary data compression technology -- or, for that matter, any reliable data compression technology -- into the MS-DOS operating system would, if implemented, have an immediate and adverse effect on the viability of STACKER as an independently marketed product for the DOS market. Indeed, at one point during the negotiations, Microsoft presented Stac with a spreadsheet analysis purporting to detail the adverse impact on sales of STACKER -- Stac's flagship product -- in the event Microsoft and Stac failed to reach an agreement and Microsoft incorporated a different data compression utility in future versions of the MS-DOS operating system. 20. In approximately April of 1992, Stac broke off further discussions with Microsoft in light of Microsoft's failure to present a proposal that offered reasonable compensation to Stac for Microsoft's use of Stac's proprietary data compression technology. 21. In approximately June of 1992, Mr. Chase advised Mr. Clow that Microsoft was obtaining data compression technology for use in MS-DOS, but that Microsoft wanted to offer Stac one last chance to reach an agreement. In the ensuing discussions, it again became clear that Microsoft had no intention of paying any compensation to Stac in exchange for Stac's proprietary data compression technology. Discussions between Stac and Microsoft thereupon terminated for the second time. 22. Shortly thereafter, it became well known to the industry that a new version of its DOS operating system, MS-DOS version 6.0 (``MS-DOS 6.0"), would be released in the first six months of 1993 and that MS-DOS 6.0 would include a data compression utility, which Microsoft was to later call ``DoubleSpace.'' 23. Before a new program (or new version of an existing program) is made available for retail distribution, the software developer will often distribute preliminary copies of the new software (the ``beta software'') to a large group of intended users (the ``beta sites"). The developer then seeks comments from the beta sites on the beta software's performance, thereby allowing it to identify and fix problems or ``bugs'' in the beta software that might have slipped through the developer's quality control procedures. Consistent with this practice, Microsoft commenced its MS-DOS 6.0 Beta Test Program in the second half of 1992. 24. On or about November 23, 1992, a telephone conference was held with Mr. Clow and Mr. Whiting of Stac, and Microsoft's Mr. Chase. During that conversation, Mr. Chase admitted that, during Microsoft's ``normal due diligence process,'' Microsoft had concluded that the DoubleSpace data compression utility of the MS-DOS 6.0 operating system software infringed Stac's '009 patent, one of the two patents in suit. Mr. Chase requested that Stac grant a license to Microsoft under Stac's '009 patent. After a brief discussion, Mr. Clow requested that Microsoft make a specific licensing proposal to Stac, and Mr. Chase agreed to do so. During this same telephone conference, Mr. Chase promised, in response to Stac's request, to make available to Stac a copy of the beta version of the MS-DOS 6.0 software. 25. Several weeks later, after not hearing back from Mr. Chase on a licensing proposal for Stac's patent, and after not receiving the promised beta version of MS-DOS 6.0, Mr. Clow wrote to Mr. Chase and again requested a copy of the MS-DOS 6.0 software. Mr. Clow wrote to Mr. Chase and again requested a copy of the MS-DOS 6.0 software. Mr. Clow explained that other software developers had access to the beta versions of MS-DOS 6.0, which was putting Stac at a competitive disadvantage. Mr. Clow also noted that Stac was still awaiting a specific licensing proposal from Microsoft for Stac's '009 patent. 26. Microsoft finally made the beta version of the MS-DOS 6.0 software available to Stac in January of 1993. At or about the same time, with respect to Microsoft's earlier admission regarding the infringement of Stac's '009 patent, Mr. Chase advised Stac in writing: ``Don't worry about the patent stuff. We are just going to keep with our changed code which does not infringe.'' 27. After receiving the beta version of MS-DOS 6.0, Stac engineers determined that, whether or not the ``code'' had in fact been changed from earlier versions, as represented by Mr. Chase, the DoubleSpace data compression utility contained in the beta version of MS-DOS 6.0 infringes upon Stac's '009 and '745 patents. 28. On or about January 15, 1993, Mr. Chase of Microsoft provided Mr. Whiting and Mr. Clow of Stac with a preliminary press release for the Microsoft Real-time Compression Interface (``MRCI''). MRCI defines a compression standard for allowing vendors to design software and hardware products that utilize or ``build'' upon the Double Space data compression utility in the MS-DOS 6.0 operating system. 29. Microsoft's preliminary press release confirms that ``DoubleSpace, the integrated data compression technology ... will be available with the next major version of MS-DOS, MS-DOS 6.'' The preliminary press release also reveals that, in an effort to have the compression technology in MS-DOS 6.0 quickly adopted as an industry standard, Microsoft is now offering to license - for free - the infringing DoubleSpace technology to independent hardware and software vendors. 30. Mr. Chase sent Microsoft's preliminary press release to Mr. Whiting and Mr. Clow for the stated purpose of having Stac approve the following proposed quote for Microsoft's ultimate press release, drafted for Stac by Microsoft: "We're excited about MS-DOS 6 and DoubleSpace because they create a large opportunity for boards, chips and add-on software to enhance the compression services that MS-DOS 6 and DoubleSpace offer ..." 31. On information and belief, Microsoft is taking the calculated risk of incorporating what it knows to be Stac's patented data compression technology in its MS-DOS 6.0 operating system in order to stimulate sales of its flagship product and respond to the intense market and financial community pressure to remain competitive and demonstrate continued growth. FIRST CAUSE OF ACTION FOR PATENT INFRINGEMENT 32. Stac repeats and realleges, as if set forth in full, paragraphs 1 through 31 of this Complaint.#} 33. On May 14, 1991, the '009 patent, entitled "Data Compression Apparatus And Method," was granted to Stac. Since its issuance, Stac has been, and continues to be, the owner of all right, title and interest in and to the '009 patent. A copy of the '009 patent is attached as Exhibit A, and incorporated herein by reference.#} 34. Defendant Microsoft is infringing the '009 patent, in this judicial district and elsewhere, in connection with its activities pertaining to the beta version of its MS-DOS 6.0 operating system software for IBM and IBM-compatible personal computers, which embodies the inventions disclosed and claimed in the '009 patent.#} 35. Unless enjoined by the Court, Microsoft will continue to infringe Stac's '009 patent.#} 36. As a direct and proximate result of Microsoft's conduct, Stac has suffered and will continue to suffer irreparable injury, for which it has no adequate remedy at law. Stac has also been damaged, and, until an injunction issues, will continue to be damaged in its business and reputation in an amount yet to be determined. Moreover, the willful and deliberate nature of Microsoft's infringement renders this an exceptional case, and thus Stac is further entitled to treble damages, as well as its actual attorneys' fees and litigation costs.#} SECOND CAUSE OF ACTION FOR PATENT INFRINGEMENT 37. Stac repeats and realleges, as if set forth in full, paragraphs 1 through 31 of this Complaint.#} 38. On October 20, 1987, the '745 patent, entitled "Data Compression System," was granted to Ferranti, plc ("Ferranti"). Ferranti subsequently assigned all right, title and interest in and to the '745 patent to Stac, which is now the owner of all right, title and interest in and to the '745 patent. A copy of the '745 patent is attached as Exhibit B, and incorporated herein by reference.#} 39. Defendant Microsoft is infringing the '745 patent, within this judicial district and elsewhere, in connection with its activities pertaining to the beta version of the MS-DOS 6.0 operating system software, which embodies the inventions disclosed and claimed in the '745 patent.#} 40. Unless enjoined by the Court, Microsoft will continue to infringe Stac's '745 patent.#} 41. As a direct and proximate result of Microsoft's conduct, Stac has suffered, and will continue to suffer, irreparable injury, for which it has no adequate remedy at law. Stac has also been damaged and, until an injunction issues, will continue to be damaged in its business and reputation in an amount yet to be determined.#} PRAYER FOR RELIEF WHEREFORE, Stac prays for judgment against defendant Microsoft as follows:#} 1. For a judicial determination and declaration that the '009 patent is valid and enforceable;#} 2. For a judicial determination and declaration that the '009 patent is infringed by the beta version of the MS-DOS 6.0 operating system software, and such other Microsoft products as may infringe;#} 3. For a judicial determination and declaration that Microsoft's infringement of either or both of the '009 and '745 patents is willful;#} 4. For a judicial determination and declaration that the '745 patent is valid and enforceable;#} 5. For a judicial determination and declaration that the '745 patent is infringed by the beta version of the MS-DOS 6.0 operating system software, and such other products as may infringe;#} 6. For an order preliminary and permanently enjoining Microsoft, its officers, directors, shareholders, agents, servants, employees and attorneys, and all entities and individuals acting in concert with them or on their behalf, from infringing the '009 and '745 patents;#} 7. For damages according to proof, trebled; 8. For Stac's attorneys' fees and litigation costs; and 9. For such other and further relief as the Court may deem just and proper.#} Dated: January 25, 1993 Respectfully submitted, IRELL & MANELLA Morgan Chu Wayne M. Barsky Mark A. Flagel Jeffrey L. Arrington Steven S. Weiner SHEA & GOULD John Kidd Nicholas L. Coch By: Morgan Chu Attorneys for Plaintiff Stac Electronics DEMAND FOR JURY TRIAL Stac demands a jury trial on all issues. Dated: January 25, 1993#} Respectfully submitted, IRELL & MANELLA Morgan Chu Wayne M. Barsky Mark A. Flagel Jeffrey L. Arrington Steven S. Weiner SHEA & GOULD John Kidd Nicholas L. Coch By: Morgan Chu Attorneys for Plaintiff Stac Electronics UNITED STATES PATENT [19] [11] Patent Number: 5,016,009 Whiting et al. [45] Date of Patent: May 14, 1991 [54] DATA COMPRESSION APPARATUS AND METHOD [75] Inventors: Douglas L. Whiting, South Pasadena;#} Glen A. George; Glen E. Ivey, both of Pasadena, all of Calif. [73] Assignee: Stac, Inc., Pasadena, Calif. [21] Appl. No.: 297,152 [22] Filed: Jan. 13, 1989 [51] Int. Cl. (5) H03M 7/40; H03L 7/00 [52] U.S. Cl. 341/67; 341/95;#} 341/106; 375/112; 370/102 [58] Field of Search 375/27, 112; 358/261.1;#} 364/715.02; 341/51, 67, 106, 95; 370/102 [56] References Cited U.S. PATENT DOCUMENTS 3,976,844 8/1976 Betz 4,021,782 5/1977 Hoerning 4,054,951 10/1977 Jackson et al. 4,412,306 10/1983 Moll 4,464,650 8/1984 Eastman et al. 341/51 4,491,934 1/1985 Heinz 4,558,302 12/1985 Welch 341/51 4,612,532 9/1986 Bacon et al. 341/90 X 4,701,745 10/1987 Waterworth 4,814,746 3/1989 Miller et al. 4,876,541 10/1989 Storer 341/67 X#} OTHER PUBLICATIONS J. Cleary et al. "Data Compression Using Adaptive Coding and Partial String Matching." IEEE Transactions on Communications, 32:396-403 (1984). M Wells. "File Compression Using Variable Length Encodings," The Computer Journal, 15:308-313 (1972). Primary Examiner - A.D. Pellinan Assistant Examiner - Sharon D. Logan Attorney, Agent, or Firm - Irell & Manella [57] ABSTRACT An apparatus and method for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a history array means. The history array means has a plurality of entries and each entry of the history array means is for storing a portion of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in a history array means for the longest data string which matches the input data string. If the matching data string is found within the history buffer means, the next step includes encoding the longest matching data string found by appending to the encoded data stream a tag indicating the longest matching data string was found and a string substitution code. If the matching data string is not found within the history array means, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag indicating that no matching data string was found and the first character of the input data string. UNITED STATES PATENT [19] [11] Patent Number: 4,701,745 Waterworth [45] Date of Patent: Oct. 20, 1987 [54] DATA COMPRESSION SYSTEM [75] Inventor: John R. Waterworth, Cheadle, England [73] Assignee: Ferranti, plc, Cheshire, England [21] Appl. No.: 835,793 [22] Filed: Mar. 3, 1986 [30] Foreign Application Priority Data Mar. 6, 1985 [GB] United Kingdom 8505790 [51] Int. Cl. (4) H03M 7/30 [52] U.S. Cl. 340/347 DD; 364/900 [58] Field of Search 340/347 DD; 235/310;#} 358/260, 261; 364/900 [56] References Cited U.S. PATENT DOCUMENTS 4,054,951 10/1977 Jackson 364/900 Primary Examiner - Charles D. Miller Attorney, Agent or Firm - Kerkam, Stowell, Kondracki & Clarke [57] ABSTRACT A data compression system includes an input store (1) for receiving and storing a plurality of bytes of data from an outside source. Data processing means for processing successive bytes of data from the input store includes circuit means (21-25) operable to check whether a sequence of bytes is identical with a sequence of bytes already processed, output means (27) operable to apply to a transfer medi um (12) each byte of data not forming part of such an identical sequence, and an encoder (26) responsive to the identification of such a sequence to apply to the transfer means (12) an identification signal which identifies both the location in the input store of the previous occurrence of the sequence of bytes and the number of bytes in the sequence.#} CONTACT: IRELL & MANELLA | Morgan Chu | Wayne M. Barsky | Mark A. Flagel | Jeffrey L. Arrington | Steven S. Weiner | 1800 Avenue of the Stars | Los Angeles, California 90067-4276 | Telephone: (310) 277-1010 | or | SHEA & GOULD | John Kidd | Nicholas L. Coch | 1251 Avenue of the Americas | New York, New York 10020 | Telephone: (212) 827-3000