{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T16:27:36Z","timestamp":1746289656959},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>\n            With the emergence of software delivery platforms, code compression has become an important system component that strongly affects performance. This article presents PPMexe, a compression mechanism for program binaries that analyzes their syntax and semantics to achieve superior compression ratios. We use the generic paradigm of prediction by partial matching (PPM) as the foundation of our compression codec. PPMexe combines PPM with two preprocessing steps: (\n            <jats:italic>i<\/jats:italic>\n            ) instruction rescheduling to improve prediction rates and (\n            <jats:italic>ii<\/jats:italic>\n            ) heuristic partitioning of a program binary into streams with high autocorrelation. We improve the traditional PPM algorithm by (\n            <jats:italic>iii<\/jats:italic>\n            ) using an additional alphabet of frequent variable-length supersymbols extracted from the input stream of fixed-length symbols. In addition, PPMexe features (\n            <jats:italic>iv<\/jats:italic>\n            ) a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a property pivotal for runtime software delivery. We implemented PPMexe for x86 binaries and tested it on several large applications. Binaries compressed using PPMexe were 18--24% smaller than files created using off-the-shelf PPMD, one of the best available compressors\n          <\/jats:p>","DOI":"10.1145\/1180475.1180478","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"3","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["PPMexe"],"prefix":"10.1145","volume":"29","author":[{"given":"Milenko","family":"Drini\u0107","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Darko","family":"Kirovski","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoi","family":"Vo","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.894158"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the USENIX Annual Technical Conference. 179--190","author":"Baker B. S.","unstructured":"Baker , B. S. and Manber , U . 1998. Deducing similarities in Java sources from bytecodes . In Proceedings of the USENIX Annual Technical Conference. 179--190 . Baker, B. S. and Manber, U. 1998. Deducing similarities in Java sources from bytecodes. In Proceedings of the USENIX Annual Technical Conference. 179--190."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/40.2_and_3.76"},{"key":"e_1_2_1_4_1","unstructured":"Burrows M. and Wheeler D. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. Digital Equipment Corporation.  Burrows M. and Wheeler D. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. Digital Equipment Corporation."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.186"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321363"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321495.321506"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/349214.349233"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258947"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/265563.265576"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301672"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502886"},{"key":"e_1_2_1_14_1","unstructured":"Gilchrist J. 2000. The archive compression test. http:\/\/compression.ca.  Gilchrist J. 2000. The archive compression test. http:\/\/compression.ca."},{"key":"e_1_2_1_15_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"1995","unstructured":"Hennessy , J. L. and Patterson , D. A . 1995 . Computer Architecture: A Quantitative Approach , 2 nd ed. Morgan Kaufman , San Francisco, CA . Hennessy, J. L. and Patterson, D. A. 1995. Computer Architecture: A Quantitative Approach, 2nd ed. Morgan Kaufman, San Francisco, CA.","edition":"2"},{"key":"e_1_2_1_16_1","volume-title":"Tech. Rep. CSL-TR-77-130","author":"Hoevel L. W.","year":"1977","unstructured":"Hoevel , L. W. and Flynn , M. J . 1977 . The structure of directly executed languages: A new theory of interpretive system design. Tech. Rep. CSL-TR-77-130 , Stanford University. Hoevel, L. W. and Flynn, M. J. 1977. The structure of directly executed languages: A new theory of interpretive system design. Tech. Rep. CSL-TR-77-130, Stanford University."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/266021.266161"},{"key":"e_1_2_1_18_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA.   Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Data Compression Conference. 98--107","author":"Howard P.","unstructured":"Howard , P. and Vitter , J . 1993. Design and analysis of fast text compression based on quasi-arithmetic coding . In Proceedings of the Data Compression Conference. 98--107 . Howard, P. and Vitter, J. 1993. Design and analysis of fast text compression based on quasi-arithmetic coding. In Proceedings of the Data Compression Conference. 98--107."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_22_1","unstructured":"Intel Corp. 1999a. http:\/\/www.intel.com\/design\/pentiumiii.  Intel Corp. 1999a. http:\/\/www.intel.com\/design\/pentiumiii."},{"key":"e_1_2_1_23_1","volume-title":"Instruction set reference manual","author":"Intel Corp. 1999b.","unstructured":"Intel Corp. 1999b. Intel architecture software developer's manual , vol. 2 : Instruction set reference manual . http:\/\/developer.intel.com\/design\/processor\/. Intel Corp. 1999b. Intel architecture software developer's manual, vol. 2: Instruction set reference manual. http:\/\/developer.intel.com\/design\/processor\/."},{"key":"e_1_2_1_24_1","unstructured":"Intel Corp. 2000. http:\/\/www.intel.com\/design\/pentium4.  Intel Corp. 2000. http:\/\/www.intel.com\/design\/pentium4."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Symposium on Microarchitecture. 204--213","author":"Kirovski D.","unstructured":"Kirovski , D. , Kin , J. , and Mangione-Smith , W. H . 1997. Procedure based program compression . In Proceedings of the International Symposium on Microarchitecture. 204--213 . Kirovski, D., Kin, J., and Mangione-Smith, W. H. 1997. Procedure based program compression. In Proceedings of the International Symposium on Microarchitecture. 204--213."},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov A. N.","year":"1965","unstructured":"Kolmogorov , A. N. 1965 . Three approaches to the quantitative definition of information . Problems Inf. Transmission 1 , 1, 1 -- 7 . Kolmogorov, A. N. 1965. Three approaches to the quantitative definition of information. Problems Inf. Transmission 1, 1, 1--7.","journal-title":"Problems Inf. Transmission"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320944"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951724"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Data Compression Conference. 306--315","author":"Lekatsas H.","unstructured":"Lekatsas , H. and Wolf , W . 1999. Random access decompression using binary arithmetic coding . In Proceedings of the Data Compression Conference. 306--315 . Lekatsas, H. and Wolf, W. 1999. Random access decompression using binary arithmetic coding. In Proceedings of the Data Compression Conference. 306--315."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229543"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the ACM IEEE International Conference on Computer-Aided Design. 393--399","author":"Liao S.","unstructured":"Liao , S. , Devadas , S. , Keutzer , K. , and Tjiang , S . 1995. Instruction selection using binate covering for code size optimization . In Proceedings of the ACM IEEE International Conference on Computer-Aided Design. 393--399 . Liao, S., Devadas, S., Keutzer, K., and Tjiang, S. 1995. Instruction selection using binate covering for code size optimization. In Proceedings of the ACM IEEE International Conference on Computer-Aided Design. 393--399."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349307"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.61469"},{"key":"e_1_2_1_34_1","unstructured":"Mohney D. 2003. It's all about the last mile. http:\/\/www.theinquirer.net.  Mohney D. 2003. It's all about the last mile. http:\/\/www.theinquirer.net."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/117009.117016"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199526"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301676"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301653"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(78)90005-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.20074"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237175"},{"key":"e_1_2_1_42_1","article-title":"Prediction and entropy of printed English. Bell","author":"Shannon C.","year":"1951","unstructured":"Shannon , C. 1951 . Prediction and entropy of printed English. Bell Syst. Tech. J. 50--64. Shannon, C. 1951. Prediction and entropy of printed English. Bell Syst. Tech. J. 50--64.","journal-title":"Syst. Tech. J. 50--64."},{"key":"e_1_2_1_43_1","volume-title":"Vulcan: Binary transformation in a distributed environment. Tech. Rep. MSR-TR-2001-50. Microsoft Research.","author":"Srivastava A.","year":"2001","unstructured":"Srivastava , A. and Vo , H . 2001 . Vulcan: Binary transformation in a distributed environment. Tech. Rep. MSR-TR-2001-50. Microsoft Research. Srivastava, A. and Vo, H. 2001. Vulcan: Binary transformation in a distributed environment. Tech. Rep. MSR-TR-2001-50. Microsoft Research."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.386"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.729791"},{"key":"e_1_2_1_46_1","volume-title":"SPEC2000 binaries. http:\/\/www.simplescalar.org.","author":"Weaver C.","year":"2000","unstructured":"Weaver , C. 2000 . SPEC2000 binaries. http:\/\/www.simplescalar.org. Weaver, C. 2000. SPEC2000 binaries. http:\/\/www.simplescalar.org."},{"key":"e_1_2_1_47_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann","author":"Witten I.","year":"1999","unstructured":"Witten , I. , Moffat , A. , and Bell , T . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann , San Francisco, CA . Witten, I., Moffat, A., and Bell, T. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Symposium on Microarchitecture. 81--91","author":"Wolfe A.","unstructured":"Wolfe , A. and Chanin , A . 1992. Executing compressed programs on an embedded RISC architecture . In Proceedings of the International Symposium on Microarchitecture. 81--91 . Wolfe, A. and Chanin, A. 1992. Executing compressed programs on an embedded RISC architecture. In Proceedings of the International Symposium on Microarchitecture. 81--91."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089008.1089012"},{"key":"e_1_2_1_50_1","article-title":"Compression of individual sequences via variable-rate coding","author":"Ziv J.","year":"1978","unstructured":"Ziv , J. and Lempel , A. 1978 . Compression of individual sequences via variable-rate coding . IEEE Trans. Inf. Theor. IT-24, 530--536. Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. IT-24, 530--536.","journal-title":"IEEE Trans. Inf. Theor. IT-24, 530--536."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1180475.1180478","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:26:37Z","timestamp":1672259197000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1180475.1180478"}},"subtitle":["Program compression"],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1145\/1180475.1180478"],"URL":"https:\/\/doi.org\/10.1145\/1180475.1180478","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]},"assertion":[{"value":"2007-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}