1、 Reference numberISO/IEC 22091:2002(E)ISO/IEC 2002INTERNATIONAL STANDARD ISO/IEC22091First edition2002-09-15Information technology Streaming Lossless Data Compression algorithm (SLDC) Technologies de linformation Algorithme de compression sans perte de donnes en mode continu (SDLC) Adopted by INCITS
2、 (InterNational Committee for Information Technology Standards) as an American National Standard.Date of ANSI Approval: 7/7/2003Published by American National Standards Institute,25 West 43rd Street, New York, New York 10036Copyright 2003 by Information Technology Industry Council (ITI).All rights r
3、eserved.These materials are subject to copyright claims of International Standardization Organization (ISO), InternationalElectrotechnical Commission (IEC), American National Standards Institute (ANSI), and Information Technology Industry Council(ITI). Not for resale. No part of this publication may
4、 be reproduced in any form, including an electronic retrieval system, withoutthe prior written permission of ITI. All requests pertaining to this standard should be submitted to ITI, 1250 Eye Street NW,Washington, DC 20005.Printed in the United States of AmericaCopyright American National Standards
5、Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) PDF disclaimer This PDF file may contain embedded typefaces. In accordance with Adobes licensing policy, this file may be printed or viewed but sh
6、all not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobes licensing policy. The ISO Central Secretariat accepts no liability in this area
7、. Adobe is a trademark of Adobe Systems Incorporated. Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by
8、 ISO member bodies. In the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below. ISO/IEC 2002 All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means, ele
9、ctronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or ISOs member body in the country of the requester. ISO copyright office Case postale 56 CH-1211 Geneva 20 Tel. + 41 22 749 01 11 Fax + 41 22 749 09 47 E-mail copyrightiso
10、.ch Web www.iso.ch Printed in Switzerland ii ISO/IEC 2002 All rights reservedCopyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) ISO/IEC 2002 All rights reserve
11、d iiiContents 1 Scope 1 2 Conformance 1 3 Normative reference 1 4 Terms and definitions 1 4.1 Access Point 1 4.2 Control Symbol 1 4.3 Copy Pointer 1 4.4 data byte 1 4.5 Data Symbol 1 4.6 Displacement Field 1 4.7 Encoded Data Stream 1 4.8 Encoded Record 1 4.9 End Marker 2 4.10 End Of Record Symbol (E
12、OR Symbol) 2 4.11 File Mark 2 4.12 File Mark Symbol 2 4.13 Flush Symbol 2 4.14 History Buffer 2 4.15 Literal 1 2 4.16 Literal 2 2 4.17 Matching String 2 4.18 Match Count 2 4.19 Match Count Field 2 4.20 Pad 2 4.21 Record 2 4.22 Record Segment 2 4.23 Reset X Symbol 2 4.24 Reset 1 Symbol 2 4.25 Reset 2
13、 Symbol 2 4.26 scheme 1 2 4.27 Scheme 1 Symbol 2 4.28 scheme 2 3 4.29 Scheme 2 Symbol 3 4.30 user data 3 5 Conventions and Notations 3 5.1 Representation of numbers 3 5.2 Names 3 6 Acronyms 3 7 Algorithm Overview 3 7.1 Scheme 1 Encoding 3 7.2 Scheme 2 Encoding 3 7.3 History Buffer 4 8 Encoding Speci
14、fication 4 8.1 User Data 4 8.2 History Buffer 4 8.3 Encoded Data Stream 4 Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) iv ISO/IEC 2002 All rights reserve
15、d8.3.1 Access Point 5 8.4 Data Symbols 5 8.4.1 Literal 1 Data Symbols 5 8.4.2 Copy Pointer Data Symbols 5 8.4.3 Literal 2 Data Symbols 6 8.5 Control Symbols 7 8.6 Pad 8 Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking
16、permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) ISO/IEC 2002 All rights reserved vForeword ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are
17、 members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other internationa
18、l organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1. International Standards are drafted in accordance with the rules given in the
19、ISO/IEC Directives, Part 3. The main task of the joint technical committee is to prepare International Standards. Draft International Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as an International Standard requires approval by at leas
20、t 75 % of the national bodies casting a vote. Attention is drawn to the possibility that some of the elements of this International Standard may be the subject of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights. ISO/IEC 22091 was prepared by ECM
21、A (as ECMA-321) and was adopted, under a special “fast-track procedure”, by Joint Technical Committee ISO/IEC JTC 1, Information Technology, in parallel with its approval by national bodies of ISO and IEC. Copyright American National Standards Institute Provided by IHS under license with ANSINot for
22、 ResaleNo reproduction or networking permitted without license from IHS-,-,-Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-INTERNATIONAL STANDARD ISO/IEC 22091:2002(E) ISO/IEC 2
23、002 All rights reserved 1Information technology Streaming Lossless Data Compression algorithm (SLDC) 1 Scope This International Standard specifies a lossless compression algorithm to reduce the number of 8-bit bytes required to represent data records and File Marks. The algorithm is known as Streami
24、ng Lossless Data Compression algorithm (SLDC). One buffer size (1 024 bytes) is specified. The numerical identifier according to ISO/IEC 11576 allocated to this algorithm is 6. 2 Conformance A compression algorithm shall be in conformance with this International Standard if its Encoded Data Stream s
25、atisfies the requirements of this International Standard. 3 Normative reference The following normative document contains provisions which, through reference in this text, constitute provisions of this International Standard. For dated references, subsequent amendments to, or revisions of, any of th
26、ese publications do not apply. However, parties to agreements based on this International Standard are encouraged to investigate the possibility of applying the most recent editions of the normative document indicated below. For undated references, the latest edition of the normative document referr
27、ed to applies. Members of ISO and IEC maintain registers of currently valid International Standards. ISO/IEC 11576:1994 Information technology Procedure for the registration of algorithms for the lossless compression of data 4 Terms and definitions For the purpose of this International Standard the
28、following terms and definitions apply. 4.1 Access Point A location in the Encoded Data Stream at which data may be decoded. 4.2 Control Symbol A Control Symbol may change the compression scheme, reset the History Buffer, mark the end of a Record, indicate a File Mark, or indicate the termination of
29、an Encoded Data Stream. 4.3 Copy Pointer A part of the Encoded Data Stream output in scheme 1 that replaces a string of data bytes with a specification of a Matching String. 4.4 data byte An element of user data that is to be encoded. 4.5 Data Symbol An element of an Encoded Record that represents o
30、ne or more data bytes. 4.6 Displacement Field A field in the Copy Pointer that specifies the location within the History Buffer of the first byte of a Matching String. 4.7 Encoded Data Stream The output stream after encoding User Data. 4.8 Encoded Record The output stream after encoding one Record o
31、f user data. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) 2 ISO/IEC 2002 All rights reserved4.9 End Marker A Control Symbol that denotes termination of a
32、n Encoded Data Stream. 4.10 End Of Record Symbol (EOR Symbol) A Control Symbol that denotes the end of a Record in the Encoded Data Stream. 4.11 File Mark A recorded element used to mark organisational boundaries (e.g. directory boundaries) in user data. 4.12 File Mark Symbol A Control Symbol in Enc
33、oded Data Stream that denotes a File Mark in user data. 4.13 Flush Symbol A Control Symbol that, if required, is followed by Pad to make the size of the Encoded Data Stream an integer multiple of 32 bits. 4.14 History Buffer A data structure where incoming data bytes are stored for use by scheme 1 c
34、ompression and decompression. 4.15 Literal 1 A part of the Encoded Data Stream, output in scheme 1, that represents a single data byte not encoded into any Copy Pointer. 4.16 Literal 2 A part of the Encoded Data Stream, output in scheme 2, that represents a single data byte. 4.17 Matching String A s
35、equence of two or more bytes in the History Buffer that is identical with a sequence of bytes in the user data. 4.18 Match Count The length, in bytes, of a Matching String. 4.19 Match Count Field That part of a Copy Pointer that specifies the Match Count. 4.20 Pad A number of bits inserted into the
36、Encoded Data Stream so that the size of Encoded Data Stream is an integer multiple of 32 bits. 4.21 Record An element of user data that contains at least one data byte. 4.22 Record Segment A section of a Record encoded in a given scheme. 4.23 Reset X Symbol A generic reference to either the Reset 1
37、Symbol or the Reset 2 Symbol. 4.24 Reset 1 Symbol A Control Symbol that indicates History Buffer reset, and that subsequent symbols are encoded in scheme 1. 4.25 Reset 2 Symbol A Control Symbol that indicates History Buffer reset, and that subsequent symbols are encoded in scheme 2. 4.26 scheme 1 A
38、compression scheme that uses a History Buffer to achieve data compression. 4.27 Scheme 1 Symbol A Control Symbol that indicates subsequent Data Symbols are either Copy Pointers or Literal 1s. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo repr
39、oduction or networking permitted without license from IHS-,-,-ISO/IEC 22091:2002(E) ISO/IEC 2002 All rights reserved 34.28 scheme 2 A packing scheme designed to encode uncompressible data with minimal expansion. 4.29 Scheme 2 Symbol A Control Symbol that indicates subsequent Data Symbols are encoded
40、 in scheme 2. 4.30 user data Information that is to be encoded, according to this compression algorithm. 5 Conventions and Notations 5.1 Representation of numbers The following conventions and notations apply in this document unless otherwise stated. The setting of bits is denoted by ZERO or ONE. Nu
41、mbers in binary notation and bit combinations are strings of digits represented by ZEROs and ONEs with the most significant bit to the left. Letters and digits in parentheses represent numbers in hexadecimal notation. All other numbers are in decimal form. 5.2 Names The names of basic elements, e.g.
42、 specific fields, are written with a capital initial letter. 6 Acronyms EOR End Of Record lsb least significant bit msb most significant bit 7 Algorithm Overview User data that is to be compressed according to this International Standard consists of Records and File Marks. Records consist of 8-bit d
43、ata bytes, and may be of any non-zero length. Data bytes may be encoded in either scheme 1 or scheme 2. 7.1 Scheme 1 Encoding There may exist within Records repeating strings of two or more data bytes such that information about the length and position of one string may be substituted in place of a
44、subsequent copy or copies of that same string. This information is known as a Copy Pointer. This International Standard allows Copy Pointer substitution when corresponding bytes of the two strings are offset by 1 to 1 023 data bytes within user data. Where string matches occur, data compression is p
45、ossible, and the number of bits of encoded data can be less than the number of bits of user data, and data compression is possible. Any data bytes that are part of a repeated string may be encoded as a Copy Pointer. Any data byte that is not encoded as a Copy Pointer is encoded as a Literal 1, in wh
46、ich a leading bit set to ZERO is added to the data byte, thereby indicating that this is a Literal 1. Regions over which Copy Pointers and literal values are encoded are defined as being encoded according to scheme 1. Scheme 1 encoding is identical with that of ISO/IEC 15200, except for the addition
47、 of Control Symbols. These are both implementations of the Lempel-Ziv 1 (LZ1) class of data compression algorithms. Following a Reset 1 Symbol or a Scheme 1 Symbol, all bytes of user data shall be encoded according to scheme 1. 7.2 Scheme 2 Encoding There may also exist within user data, regions in
48、which few such repeating strings exist. Where there are no repeating strings, scheme1 encoding requires a 9-bit Literal 1value in the Encoded Data Stream for every data byte. This results in an Encoded Data Stream that has 12,5 % more bits than the user data. In order to avoid this data expansion, s
49、cheme 2 encoding may be used. In scheme 2 encoding, data bytes are copied to the output bit stream. In order for a decoder to distinguish a data byte set to (FF) from a Control Symbol, a trailing bit set to ZERO is encoded following every data byte of (FF). For random data, this tends to produce an Encoded Data Stream that has about 0,05 % more bits than the user data. Follo
