View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   https://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.commons.compress.harmony.pack200;
20  
21  import java.io.IOException;
22  import java.io.InputStream;
23  import java.util.Arrays;
24  
25  /**
26   * A PopulationCodec is a Codec that is well suited to encoding data that shows statistical or repetitive patterns, containing for example a few numbers which
27   * are repeated a lot throughout the set, but not necessarily sequentially.
28   */
29  public class PopulationCodec extends Codec {
30  
31      private final Codec favouredCodec;
32      private Codec tokenCodec;
33      private final Codec unfavouredCodec;
34      private int l;
35      private int[] favoured;
36  
37      public PopulationCodec(final Codec favouredCodec, final Codec tokenCodec, final Codec unvafouredCodec) {
38          this.favouredCodec = favouredCodec;
39          this.tokenCodec = tokenCodec;
40          this.unfavouredCodec = unvafouredCodec;
41      }
42  
43      public PopulationCodec(final Codec favouredCodec, final int l, final Codec unfavouredCodec) {
44          if (l >= 256 || l <= 0) {
45              throw new IllegalArgumentException("L must be between 1..255");
46          }
47          this.favouredCodec = favouredCodec;
48          this.l = l;
49          this.unfavouredCodec = unfavouredCodec;
50      }
51  
52      @Override
53      public int decode(final InputStream in) throws IOException, Pack200Exception {
54          throw new Pack200Exception("Population encoding does not work unless the number of elements are known");
55      }
56  
57      @Override
58      public int decode(final InputStream in, final long last) throws IOException, Pack200Exception {
59          throw new Pack200Exception("Population encoding does not work unless the number of elements are known");
60      }
61  
62      @Override
63      public int[] decodeInts(final int n, final InputStream in) throws IOException, Pack200Exception {
64          lastBandLength = 0;
65          favoured = new int[check(n, in)]; // there must be <= n values, but probably a lot
66          // less
67          final int[] result;
68          // read table of favorites first
69          int smallest = Integer.MAX_VALUE;
70          int absoluteSmallest;
71          int last = 0;
72          int value = 0;
73          int absoluteValue;
74          int k = -1;
75          while (true) {
76              value = favouredCodec.decode(in, last);
77              if (k > -1 && (value == smallest || value == last)) {
78                  break;
79              }
80              favoured[++k] = value;
81              absoluteSmallest = Math.abs(smallest);
82              absoluteValue = Math.abs(value);
83              if (absoluteSmallest > absoluteValue) {
84                  smallest = value;
85              } else if (absoluteSmallest == absoluteValue) {
86                  // ensure that -X and +X -> +X
87                  smallest = absoluteSmallest;
88              }
89              last = value;
90          }
91          lastBandLength += k;
92          // if tokenCodec needs to be derived from the T, L and K values
93          if (tokenCodec == null) {
94              if (k < 256) {
95                  tokenCodec = BYTE1;
96              } else {
97                  // if k >= 256, b >= 2
98                  int b = 1;
99                  BHSDCodec codec;
100                 while (++b < 5) {
101                     codec = new BHSDCodec(b, 256 - l, 0);
102                     if (codec.encodes(k)) {
103                         tokenCodec = codec;
104                         break;
105                     }
106                 }
107                 if (tokenCodec == null) {
108                     throw new Pack200Exception("Cannot calculate token codec from " + k + " and " + l);
109                 }
110             }
111         }
112         // read favorites
113         lastBandLength += n;
114         result = tokenCodec.decodeInts(n, in);
115         // read unfavorites
116         last = 0;
117         for (int i = 0; i < n; i++) {
118             final int index = result[i];
119             if (index == 0) {
120                 lastBandLength++;
121                 result[i] = last = unfavouredCodec.decode(in, last);
122             } else {
123                 result[i] = favoured[index - 1];
124             }
125         }
126         return result;
127     }
128 
129     @Override
130     public byte[] encode(final int value) throws Pack200Exception {
131         throw new Pack200Exception("Population encoding does not work unless the number of elements are known");
132     }
133 
134     @Override
135     public byte[] encode(final int value, final int last) throws Pack200Exception {
136         throw new Pack200Exception("Population encoding does not work unless the number of elements are known");
137     }
138 
139     public byte[] encode(final int[] favoured, final int[] tokens, final int[] unfavoured) throws Pack200Exception {
140         final int[] favoured2 = Arrays.copyOf(favoured, favoured.length + 1);
141         favoured2[favoured2.length - 1] = favoured[favoured.length - 1]; // repeat last value;
142         final byte[] favouredEncoded = favouredCodec.encode(favoured2);
143         final byte[] tokensEncoded = tokenCodec.encode(tokens);
144         final byte[] unfavouredEncoded = unfavouredCodec.encode(unfavoured);
145         final byte[] band = new byte[favouredEncoded.length + tokensEncoded.length + unfavouredEncoded.length];
146         System.arraycopy(favouredEncoded, 0, band, 0, favouredEncoded.length);
147         System.arraycopy(tokensEncoded, 0, band, favouredEncoded.length, tokensEncoded.length);
148         System.arraycopy(unfavouredEncoded, 0, band, favouredEncoded.length + tokensEncoded.length, unfavouredEncoded.length);
149         return band;
150     }
151 
152     public int[] getFavoured() {
153         return favoured;
154     }
155 
156     public Codec getFavouredCodec() {
157         return favouredCodec;
158     }
159 
160     public Codec getTokenCodec() {
161         return tokenCodec;
162     }
163 
164     public Codec getUnfavouredCodec() {
165         return unfavouredCodec;
166     }
167 }