Java bytecode compression for low-end embedded systems

ABSTRACT

A program executing on a low-end embedded system, such as a smart-card, faces scarce memory resources and fixed execution time constraints. We demonstrate that factorization of common instruction sequences in Java bytecode allows the memory footprint to be reduced, on average, to 85% of its original size, with a minimal execution time penalty. While preserving Java compatibility, our solution requires only a few modifications which are straightforward to implement in any JVM used in a low-end embedded system.

REFERENCES

• 1: Denis N. Antonioli , Markus Pilz, Analysis of the Java Class File Format, University of Zurich, 1998
• 2: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: Quetzalcoatl Bradley , R. Nigel Horspool , Jan Vitek, JAZZ: an efficient compressed format for Java archive files, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.7, November 30-December 03, 1998, Toronto, Ontario, Canada
• 4: Clausen, L. R. 1997. A Java bytecode optimizer using side-e ect analysis. Concurrency: Practice & Experience 9, 11 (Nov.), 1031-1045.
• 5: Clausen, L. R., Schultz, U., Consel, C., and Muller, G. 1998. Java bytecode compression for embedded systems. Research Report 3578, INRIA, Rennes, France. Dec.
• 6: Dallas Semiconductor Corp. 1998. Java-Powered Decoder Ring. Dallas Semiconductor Corp. URL: http://www.ibutton.com/jring_facts.html.
• 7: Dallas Semiconductor Corp. 1999. Java-Powered Ring Download Site. URL: http://www.ibutton.com/jiblet.
• 8: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, ACM SIGPLAN Notices, v.32 n.5, p.358-365, May 1997
• 9: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 10: Christopher W. Fraser , David R. Hanson, A code generation interface for ANSI C, Software—Practice & Experience, v.21 n.9, p.963-988, Sept. 1991 [doi>10.1002/spe.4380210906]
• 11: Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
• 12: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 15: Huffman, D. A. 1952. A method for the construction of minimum-redundancy codes. Proceedings of the Institute for Radio Engineering 40, 9 (Sept.), 1098-1101.
• 16: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 17: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 18: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 19: Gilles Muller , Ulrik Pagh Schultz, Harissa: A Hybrid Approach to Java Execution, IEEE Software, v.16 n.2, p.44-51, March 1999 [doi>10.1109/52.754052]
• 20: Pendragon Software. 1997. Ca eineMark 3.0. URL: http://www.webfayre.com/pendragon/cm3/index.html.
• 21: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 22: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 23: Derek Rayside , Evan Mamas , Erik Hons, Compact Java binaries for embedded systems, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.9, November 08-11, 1999, Mississauga, Ontario, Canada
• 24: Sun Microsystems, Inc. 1997. JavaCard 2.0 Language Subset and Virtual Machine Speci cation, 1.0 ed. Sun Microsystems, Inc. URL: http://www.javasoft.com/products/javacard.
• 25: Sun Microsystems, Inc. 1998a. Embedded Java Speci cation, 1.0 ed. Sun Microsystems, Inc. URL: http://java.sun.com/products/embeddedjava/note.html.
• 26: Sun Microsystems, Inc. 1998b. Java Card API 2.0 Reference Implementation, Developer Release 2 ed. Sun Microsystems, Inc. URL: http://www.javasoft.com/products/javacard.
• 27: Sun Microsystems, Inc. 1998c. The Java Developers Kit 1.0.2. Sun Microsystems, Inc. URL: http://java.sun.com/products/jdk/1.0.2/.
• 28: Sun Microsystems, Inc. 1999a. Java Embedded Server. Sun Microsystems, Inc. URL: http://www.sun.com/software/embeddedserver.
• 29: Sun Microsystems, Inc. 1999b. JavaCard 2.1 Application Programming Interface Speci cation. Sun Microsystems, Inc. URL: http://www.javasoft.com/products/javacard.
• 30: Sun Microsystems, Inc. 1999c. JavaCard 2.1 Runtime Environment (JCRE) Speci cation. Sun Microsystems, Inc. URL: http://www.javasoft.com/products/javacard.
• 31: Sun Microsystems, Inc. 1999d. JavaCard 2.1 Virtual Machine Speci cation. Sun Microsystems, Inc. URL: http://www.javasoft.com/products/javacard.
• 32: Sun Microsystems, Inc. 2000. JavaCard 2.1 development kit. URL: http://www.javasoft.com/products/javacard.
• 33: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, ACM SIGPLAN Notices, v.32 n.10, p.271-285, Oct. 1997
• 34: Visa International Service Association 1998. Visa Open Platform Card Version 1.0 Implementation for Applet Developers. Visa International Service Association. URL: http://www.visa.com/cgi-bin/vee/nt/suppliers/open/main.html.
• 35: Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable rate encoding. IEEE Transactions on Information Theory 24, 530-536.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters; Run-time environments

General Terms:
Algorithms, Languages, Performance

Keywords:
Java bytecode, code compression, embedded systems