dain / snappy Goto Github PK

View Code? Open in Web Editor NEW

358.0 31.0 72.0 2.14 MB

Port of Snappy to Java

License: Apache License 2.0

Java 100.00%

snappy's Introduction

🚚 MOVED 🚚

Future development of Snappy without JNI has moved to aircompressor

Snappy in Java

This is a rewrite (port) of Snappy written in pure Java. This compression code produces a byte-for-byte exact copy of the output created by the original C++ code, and extremely fast.

Performance

The Snappy micro-benchmark has been ported, and can be used to measure the performance of this code against the excellent Snappy JNI wrapper from xerial. As you can see in the results below, the pure Java port is 20-30% faster for block compress, 0-10% slower for block uncompress, and 0-5% slower for round-trip block compression. These results were run with Java 7 on a Core i7, 64-bit Mac.

As a second more independent test, the performance has been measured using the Ning JVM compression benchmark against Snappy JNI, and the pure Java Ning LZF codec. The results show that the pure Java Snappy is 20-30% faster than JNI Snappy for compression, and is typically 10-20% slower for decompression. Both, the pure Java Snappy and JNI Snappy implementations are faster that the Ning LZF codec. These results were run with Java 6 on a Core i7, 64-bit Mac.

The difference in performance between these two tests is due to the difference in JVM version; Java 7 is consistently 5-10% faster than Java 6 in the compression code. As with all benchmarks your mileage will vary, so test with your actual use case.

Block Compress


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%   294.9MB/s   384.8MB/s  +30.5%  html
urls       702087     49.1%     49.1%   178.7MB/s   226.5MB/s  +26.8%  urls
jpg        126958      0.1%      0.1%     2.7GB/s     3.2GB/s  +17.4%  jpg (not compressible)
pdf         94330     17.9%     17.9%   642.4MB/s   910.3MB/s  +41.7%  pdf
html4      409600     76.4%     76.4%   289.2MB/s   377.3MB/s  +30.5%  html4
cp          24603     51.9%     51.9%   166.4MB/s   233.7MB/s  +40.5%  cp
c           11150     57.6%     57.6%   177.1MB/s   295.4MB/s  +66.8%  c
lsp          3721     51.6%     51.6%   245.5MB/s   278.0MB/s  +13.2%  lsp
xls       1029744     58.7%     58.7%   263.0MB/s   292.5MB/s  +11.2%  xls
txt1       152089     40.2%     40.2%   116.8MB/s   163.1MB/s  +39.7%  txt1
txt2       125179     35.9%     35.9%   112.5MB/s   153.4MB/s  +36.3%  txt2
txt3       426754     42.9%     42.9%   123.3MB/s   169.8MB/s  +37.6%  txt3
txt4       481861     31.7%     31.7%   107.8MB/s   146.2MB/s  +35.6%  txt4
bin        513216     81.8%     81.8%   413.1MB/s   497.8MB/s  +20.5%  bin
sum         38240     48.1%     48.1%   162.4MB/s   213.9MB/s  +31.7%  sum
man          4227     40.6%     40.6%   194.6MB/s   241.7MB/s  +24.2%  man
pb         118588     76.8%     76.8%   363.7MB/s   450.3MB/s  +23.8%  pb
gaviota    184320     61.7%     61.7%   166.7MB/s   253.7MB/s  +52.2%  gaviota

Block Uncompress


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%     1.5GB/s     1.3GB/s  -12.2%  html
urls       702087     49.1%     49.1%   969.2MB/s   827.5MB/s  -14.6%  urls
jpg        126958      0.1%      0.1%    18.6GB/s    19.4GB/s   +4.2%  jpg (not compressible)
pdf         94330     17.9%     17.9%     4.1GB/s     3.7GB/s   -8.8%  pdf
html4      409600     76.4%     76.4%     1.5GB/s     1.2GB/s  -16.8%  html4
cp          24603     51.9%     51.9%   965.2MB/s   956.0MB/s   -1.0%  cp
c           11150     57.6%     57.6%   989.1MB/s   924.9MB/s   -6.5%  c
lsp          3721     51.6%     51.6%   991.6MB/s   964.8MB/s   -2.7%  lsp
xls       1029744     58.7%     58.7%   798.4MB/s   747.3MB/s   -6.4%  xls
txt1       152089     40.2%     40.2%   643.8MB/s   580.8MB/s   -9.8%  txt1
txt2       125179     35.9%     35.9%   610.0MB/s   549.6MB/s   -9.9%  txt2
txt3       426754     42.9%     42.9%   683.8MB/s   614.4MB/s  -10.2%  txt3
txt4       481861     31.7%     31.7%   565.4MB/s   505.5MB/s  -10.6%  txt4
bin        513216     81.8%     81.8%     1.5GB/s     1.2GB/s  -20.4%  bin
sum         38240     48.1%     48.1%   838.1MB/s   771.6MB/s   -7.9%  sum
man          4227     40.6%     40.6%   856.9MB/s   847.2MB/s   -1.1%  man
pb         118588     76.8%     76.8%     1.7GB/s     1.5GB/s  -12.9%  pb
gaviota    184320     61.7%     61.7%   769.1MB/s   693.4MB/s   -9.9%  gaviota

Block Round Trip


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%   300.3MB/s   287.1MB/s   -4.4%  html
urls       702087     49.1%     49.1%   182.7MB/s   177.0MB/s   -3.2%  urls
jpg        126958      0.1%      0.1%     2.6GB/s     2.6GB/s   +1.1%  jpg (not compressible)
pdf         94330     17.9%     17.9%   695.3MB/s   680.0MB/s   -2.2%  pdf
html4      409600     76.4%     76.4%   296.4MB/s   282.1MB/s   -4.8%  html4
cp          24603     51.9%     51.9%   177.0MB/s   172.5MB/s   -2.5%  cp
c           11150     57.6%     57.6%   221.7MB/s   218.3MB/s   -1.5%  c
lsp          3721     51.6%     51.6%   217.3MB/s   216.3MB/s   -0.5%  lsp
xls       1029744     58.7%     58.7%   213.3MB/s   209.9MB/s   -1.6%  xls
txt1       152089     40.2%     40.2%   129.4MB/s   126.3MB/s   -2.4%  txt1
txt2       125179     35.9%     35.9%   121.7MB/s   118.8MB/s   -2.4%  txt2
txt3       426754     42.9%     42.9%   135.2MB/s   132.8MB/s   -1.8%  txt3
txt4       481861     31.7%     31.7%   115.2MB/s   113.0MB/s   -1.9%  txt4
bin        513216     81.8%     81.8%   371.2MB/s   350.7MB/s   -5.5%  bin
sum         38240     48.1%     48.1%   164.2MB/s   160.0MB/s   -2.6%  sum
man          4227     40.6%     40.6%   184.8MB/s   185.3MB/s   +0.3%  man
pb         118588     76.8%     76.8%   344.1MB/s   326.3MB/s   -5.2%  pb
gaviota    184320     61.7%     61.7%   188.0MB/s   185.2MB/s   -1.5%  gaviota

Stream Format

There is no defined stream format for Snappy, but there is an effort to create a common format with the Google Snappy project.

The stream format used in this library has a couple of unique features not found in the other Snappy stream formats. Like the other formats, the user input is broken into blocks and each block is compressed. If the compressed block is smaller that the user input, the compressed block is written, otherwise the uncompressed original is written. This dramatically improves the speed of uncompressible input such as JPG images. Additionally, a checksum of the user input data for each block is written to the stream. This safety check assures that the stream has not been corrupted in transit or by a bad Snappy implementation. Finally, like gzip, compressed Snappy files can be concatenated together without issue, since the input stream will ignore a Snappy stream header in the middle of a stream. This makes combining files in Hadoop and S3 trivial.

The the SnappyOutputStream javadocs contain formal definition of the stream format.

Stream Performance

The streaming mode performance can not be directly compared to other compression algorithms since most formats do not contain a checksum. The basic streaming code is significantly faster that the Snappy JNI library due to the completely unoptimized stream implementation in Snappy JNI, but once the check sum is enabled the performance drops off by about 20%.

Stream Compress (no checksums)


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%   275.8MB/s   373.5MB/s  +35.4%  html
urls       702087     49.1%     49.1%   176.5MB/s   225.2MB/s  +27.6%  urls
jpg        126958      0.1%     -0.0%     1.7GB/s     2.0GB/s  +15.8%  jpg (not compressible)
pdf         94330     17.8%     16.0%   557.2MB/s   793.2MB/s  +42.4%  pdf
html4      409600     76.4%     76.4%   281.0MB/s   369.9MB/s  +31.7%  html4
cp          24603     51.8%     51.8%   151.7MB/s   214.3MB/s  +41.3%  cp
c           11150     57.4%     57.5%   149.1MB/s   243.3MB/s  +63.1%  c
lsp          3721     51.1%     51.2%   141.3MB/s   181.1MB/s  +28.2%  lsp
xls       1029744     58.6%     58.6%   253.9MB/s   290.5MB/s  +14.4%  xls
txt1       152089     40.2%     40.2%   114.8MB/s   159.4MB/s  +38.8%  txt1
txt2       125179     35.9%     35.9%   110.0MB/s   150.4MB/s  +36.7%  txt2
txt3       426754     42.9%     42.9%   121.0MB/s   167.9MB/s  +38.8%  txt3
txt4       481861     31.6%     31.6%   105.1MB/s   143.2MB/s  +36.2%  txt4
bin        513216     81.8%     81.8%   387.7MB/s   484.5MB/s  +25.0%  bin
sum         38240     48.1%     48.1%   153.0MB/s   203.1MB/s  +32.8%  sum
man          4227     40.2%     40.3%   125.9MB/s   171.9MB/s  +36.5%  man
pb         118588     76.8%     76.8%   342.2MB/s   431.4MB/s  +26.1%  pb
gaviota    184320     61.7%     61.7%   161.1MB/s   246.1MB/s  +52.7%  gaviota

Stream Uncompress (no checksums)


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%     1.2GB/s     1.2GB/s   +0.4%  html
urls       702087     49.1%     49.1%   853.9MB/s   786.6MB/s   -7.9%  urls
jpg        126958      0.1%     -0.0%     3.0GB/s    10.3GB/s +239.0%  jpg (not compressible)
pdf         94330     17.8%     16.0%     2.0GB/s     3.4GB/s  +71.5%  pdf
html4      409600     76.4%     76.4%     1.2GB/s     1.1GB/s   -8.4%  html4
cp          24603     51.8%     51.8%   785.2MB/s   905.6MB/s  +15.3%  cp
c           11150     57.4%     57.5%   778.9MB/s   889.7MB/s  +14.2%  c
lsp          3721     51.1%     51.2%   739.0MB/s   905.5MB/s  +22.5%  lsp
xls       1029744     58.6%     58.6%   730.3MB/s   718.8MB/s   -1.6%  xls
txt1       152089     40.2%     40.2%   582.4MB/s   559.0MB/s   -4.0%  txt1
txt2       125179     35.9%     35.9%   540.7MB/s   526.4MB/s   -2.6%  txt2
txt3       426754     42.9%     42.9%   620.5MB/s   583.9MB/s   -5.9%  txt3
txt4       481861     31.6%     31.6%   519.4MB/s   487.0MB/s   -6.2%  txt4
bin        513216     81.8%     81.8%     1.2GB/s     1.1GB/s  -11.6%  bin
sum         38240     48.1%     48.1%   693.4MB/s   742.4MB/s   +7.1%  sum
man          4227     40.2%     40.3%   637.3MB/s   784.3MB/s  +23.1%  man
pb         118588     76.8%     76.8%     1.4GB/s     1.4GB/s   +0.4%  pb
gaviota    184320     61.7%     61.7%   688.5MB/s   668.2MB/s   -3.0%  gaviota

Stream RoundTrip (no checksums)


                        JNI      Java         JNI        Java
Input        Size  Compress  Compress  Throughput  Throughput  Change
---------------------------------------------------------------------
html       102400     76.4%     76.4%   223.8MB/s   272.5MB/s  +21.8%  html
urls       702087     49.1%     49.1%   142.8MB/s   174.1MB/s  +22.0%  urls
jpg        126958      0.1%     -0.0%     1.1GB/s     1.6GB/s  +52.1%  jpg (not compressible)
pdf         94330     17.8%     16.0%   421.9MB/s   610.1MB/s  +44.6%  pdf
html4      409600     76.4%     76.4%   226.2MB/s   275.5MB/s  +21.8%  html4
cp          24603     51.8%     51.8%   125.3MB/s   160.3MB/s  +27.9%  cp
c           11150     57.4%     57.5%   125.1MB/s   183.2MB/s  +46.5%  c
lsp          3721     51.1%     51.2%   130.6MB/s   149.5MB/s  +14.5%  lsp
xls       1029744     58.6%     58.6%   188.2MB/s   206.1MB/s   +9.5%  xls
txt1       152089     40.2%     40.2%    95.3MB/s   123.3MB/s  +29.4%  txt1
txt2       125179     35.9%     35.9%    91.4MB/s   116.8MB/s  +27.9%  txt2
txt3       426754     42.9%     42.9%   101.3MB/s   130.3MB/s  +28.6%  txt3
txt4       481861     31.6%     31.6%    87.9MB/s   111.1MB/s  +26.3%  txt4
bin        513216     81.8%     81.8%   294.7MB/s   337.9MB/s  +14.7%  bin
sum         38240     48.1%     48.1%   122.9MB/s   152.9MB/s  +24.3%  sum
man          4227     40.2%     40.3%   113.0MB/s   139.1MB/s  +23.1%  man
pb         118588     76.8%     76.8%   269.5MB/s   313.8MB/s  +16.4%  pb
gaviota    184320     61.7%     61.7%   131.1MB/s   180.3MB/s  +37.6%  gaviota

snappy's People

Contributors

Stargazers

Watchers

snappy's Issues

Infinity loop in incrementalCopyFastPath

Hi there,
I identified infinity loop in incrementalCopyFastPath in our application.
Call stack of blocked thread:

at org.iq80.snappy.SnappyDecompressor.incrementalCopyFastPath([BIII)V (SnappyDecompressor.java:341)
at org.iq80.snappy.SnappyDecompressor.decompressAllTags([BII[BI)I (SnappyDecompressor.java:174)
at org.iq80.snappy.SnappyDecompressor.uncompress([BII[BI)I (SnappyDecompressor.java:76)
at org.iq80.snappy.Snappy.uncompress([BII[BI)I (Snappy.java:91)
at org.iq80.snappy.AbstractSnappyInputStream.ensureBuffer()Z (AbstractSnappyInputStream.java:250)
at org.iq80.snappy.AbstractSnappyInputStream.read([BII)I (AbstractSnappyInputStream.java:139)
at org.iq80.snappy.SnappyFramedInputStream.read([BII)I (SnappyFramedInputStream.java:32)
at java.io.InputStream.read([B)I (InputStream.java:82)
at com.google.common.io.ByteStreams.copy(Ljava/io/InputStream;Ljava/io/OutputStream;)J (ByteStreams.java:70)
...

I think that problem can be related to comment in C version of snappy - https://github.com/google/snappy/blob/master/snappy.cc#L1038

IWA files support

Hey!
Does your library support .iwa (custom framed format) compression?
more about .iwa : https://github.com/obriensp/iWorkFileFormat/blob/master/Docs/index.md#iwa

Snappy causes SIGBUS jvm crasher on HP-UX via UnsafeMemory.loadInt()

Steps to reproduce:

Install HP-UX Java 7 (e.g. from “Itanium_JDK_JRE_7.0.09_-_Feb_2014_Z7550-01326_java_17009_ia.depot”) to a local folder.
Set JDK_HOME to the above folder.
Download CLion for Linux, from jetbrains.com > Products > CLion > Early Access Program (EAP); gunzip and “tar xvf” to unpack (e.g. to /opt).
Run “/opt/clion-140.569.17/bin/clion.sh”. Deselect all plug-ins.
It appears necessary to create or open a project (failure occurs when opening a project).

Snippet from hs_err.log file:
Current thread (01370200): JavaThread "ApplicationImpl pooled thread 3" [_thread_in_vm, id=30, lwp_id=4383651, stack(2d601000,2d641000)]

siginfo:si_signo=SIGBUS: si_errno=0, si_code=1 (BUS_ADRALN), si_addr=2f4b204d

Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
j sun.misc.Unsafe.getInt(Ljava/lang/Object;J)I+0
j org.iq80.snappy.UnsafeMemory.loadInt([BI)I+50
j org.iq80.snappy.SnappyInternalUtils.loadInt([BI)I+5
j org.iq80.snappy.SnappyCompressor.findCandidate([BIIII[SI)[I+19
j org.iq80.snappy.SnappyCompressor.compressFragment([BII[BI[S)I+157
j org.iq80.snappy.SnappyCompressor.compress([BII[BI)I+63
j org.iq80.snappy.Snappy.compress([BII[BI)I+6
j org.iq80.snappy.SnappyOutputStream.writeCompressed([BII)V+27
j org.iq80.snappy.SnappyOutputStream.flushBuffer()V+17
j org.iq80.snappy.SnappyOutputStream.flush()V+18
j sun.nio.cs.StreamEncoder.implFlush()V+15
j sun.nio.cs.StreamEncoder.flush()V+12
j java.io.OutputStreamWriter.flush()V+4
j org.jdom.output.XMLOutputter.output(Lorg/jdom/Element;Ljava/io/Writer;)V+12
j com.intellij.openapi.components.impl.stores.StateMap.a(Lorg/jdom/Element;)[B+85
j com.intellij.openapi.components.impl.stores.StateMap.getStateAndArchive(Ljava/lang/String;)Lorg/jdom/Element;+68

HP has kindly provided some analysis:

In our internal discussions, we have arrived at the following conclusions (by understanding the code of snappy):
https://github.com/dain/snappy/blob/master/src/main/java/org/iq80/snappy/SnappyOutputStream.java & http://codenav.org/code.html?project=/org/iq80/snappy/snappy/0.1 .
In the call stack that we have seen:
#31 0x2000000073405c00 in interpreted frame: org.iq80.snappy.SnappyOutputStream::flushBuffer () ->void bci: 17

Provides the request to write buffer. The buffer in SnappyOutputStream.java is as follows:
private final byte[] buffer;

This buffer is passed between all the methods until it reaches:
#20
#21 0x60000000d56701e0:0 in Unsafe_GetInt () at /wsp/jinteg/SVN/jinteg_h7.0.11.rc1b1/hotspot/src/share/vm/prims/unsafe.cpp:396
#22 0x2000000073400d70 in Java native_call_stub frame
#23 0x2000000073413b70 in JNI frame: sun.misc.Unsafe::getInt (java.lang.Object, long) ->int
#24 0x2000000073405aa0 in interpreted frame: org.iq80.snappy.UnsafeMemory::loadInt (byte[], int) ->int bci: 50
#25 0x2000000073405de0 in interpreted frame: org.iq80.snappy.SnappyInternalUtils::loadInt (byte[], int) ->int bci: 5

Causing the exception (which you have observed). In the Java API code in file jdk/src/share/classes/sun/misc/Unsafe.java (available for your reference through OpenJDK) contains the following comments before method getInt():

    // These work on object fields in the Java heap.
    // They will not work on elements of packed arrays.
   Fetches a value from a given Java variable.
   More specifically, fetches a field or array element within the given
   object <code>o</code> at the given offset, or (if <code>o</code> is
   null) from the memory address whose numerical value is the given
   offset.
   <p>
   The results are undefined unless one of the following cases is true:
   <ul>
   <li>The offset was obtained from {@link #objectFieldOffset} on
   the {@link java.lang.reflect.Field} of some Java field and the object
   referred to by <code>o</code> is of a class compatible with that
   field's class.

   <li>The offset and object reference <code>o</code> (either null or
   non-null) were both obtained via {@link #staticFieldOffset}
   and {@link #staticFieldBase} (respectively) from the
   reflective {@link Field} representation of some Java field.

   <li>The object referred to by <code>o</code> is an array, and the offset
   is an integer of the form <code>B+N*S</code>, where <code>N</code> is
   a valid index into the array, and <code>B</code> and <code>S</code> are
   the values obtained by {@link #arrayBaseOffset} and {@link
   #arrayIndexScale} (respectively) from the array's class.  The value
   referred to is the <code>N</code><em>th</em> element of the array.

   </ul>
   <p>
   If one of the above cases is true, the call references a specific Java
   variable (field or array element). However, the results are undefined
   if that variable is not in fact of the type returned by this method.
   <p>
'''

The code in snappy calls getInt with an arbitrary offset, not obtained by any of the methods described above (apparently the only available documentation for this). The behavior for such invocation of sun.misc.Unsafe::getInt() is undefined regardless of the platform it is invoked in.


Note also that HP-UX Itanium is a big-endian architecture. See:
https://github.com/dain/snappy/commit/a7c9c3cdbd6a0d997975ccbde5c946e07c1684e2 

This patch may not yet be in the snappy.jar bundled with JetBrains' CLion, and may work around the issue.

Implement NIO channels interfaces and add utility bulk transfer methods

Change AbstractSnappyInputStream to also implement ReadableByteChannel and have utility transfer methods that will write the entire (uncompressed) content to a given OutputStream or WritableByteChannel.

Change AbstractSnappyOutputStream to also implement WritableByteChannel and have utility transfer methods that will read from an InputStream or ReadableByteChannel and compress to the target.

While it is possible to accomplish this using Channels and utilities such as guava ByteStreams, doing it here eliminates some of the buffer copying required.

mvn package does not build the jar

Please, observe:

o:\java\snappy-0.3>mvn package
[INFO] Scanning for projects...
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] Building snappy 0.3
[INFO] ------------------------------------------------------------------------
[INFO]
[INFO] --- maven-enforcer-plugin:1.0:enforce (enforce-versions) @ snappy ---
[INFO]
[INFO] --- maven-resources-plugin:2.4.3:resources (default-resources) @ snappy ---
[INFO] Using 'UTF-8' encoding to copy filtered resources.
[INFO] skip non existing resourceDirectory o:\java\snappy-0.3\src\main\resources
[INFO]
[INFO] --- maven-compiler-plugin:2.3.2:compile (default-compile) @ snappy ---
[INFO] Nothing to compile - all classes are up to date
[INFO]
[INFO] --- maven-resources-plugin:2.4.3:testResources (default-testResources) @ snappy ---
[INFO] Using 'UTF-8' encoding to copy filtered resources.
[INFO] skip non existing resourceDirectory o:\java\snappy-0.3\src\test\resources
[INFO]
[INFO] --- maven-compiler-plugin:2.3.2:testCompile (default-testCompile) @ snappy ---
[INFO] Nothing to compile - all classes are up to date
[INFO]
[INFO] --- maven-surefire-plugin:2.8.1:test (default-test) @ snappy ---
[INFO] Surefire report directory: o:\java\snappy-0.3\target\surefire-reports

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running TestSuite
java.lang.reflect.InvocationTargetException
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at org.xerial.snappy.SnappyLoader.loadNativeLibrary(SnappyLoader.java:317)
        at org.xerial.snappy.SnappyLoader.load(SnappyLoader.java:219)
        at org.xerial.snappy.Snappy.<clinit>(Snappy.java:44)
        at org.iq80.snappy.SnappyTest.verifyCompression(SnappyTest.java:75)
        at org.iq80.snappy.SnappyTest.verifyCompression(SnappyTest.java:69)
        at org.iq80.snappy.SnappyTest.testByteForByteOutputSyntheticData(SnappyTest.java:39)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at org.testng.internal.MethodInvocationHelper.invokeMethod(MethodInvocationHelper.java:76)
        at org.testng.internal.Invoker.invokeMethod(Invoker.java:673)
        at org.testng.internal.Invoker.invokeTestMethod(Invoker.java:846)
        at org.testng.internal.Invoker.invokeTestMethods(Invoker.java:1170)
        at org.testng.internal.TestMethodWorker.invokeTestMethods(TestMethodWorker.java:125)
        at org.testng.internal.TestMethodWorker.run(TestMethodWorker.java:109)
        at org.testng.TestRunner.runWorkers(TestRunner.java:1147)
        at org.testng.TestRunner.privateRun(TestRunner.java:749)
        at org.testng.TestRunner.run(TestRunner.java:600)
        at org.testng.SuiteRunner.runTest(SuiteRunner.java:317)
        at org.testng.SuiteRunner.runSequentially(SuiteRunner.java:312)
        at org.testng.SuiteRunner.privateRun(SuiteRunner.java:274)
        at org.testng.SuiteRunner.run(SuiteRunner.java:223)
        at org.testng.SuiteRunnerWorker.runSuite(SuiteRunnerWorker.java:52)
        at org.testng.SuiteRunnerWorker.run(SuiteRunnerWorker.java:86)
        at org.testng.TestNG.runSuitesSequentially(TestNG.java:1039)
        at org.testng.TestNG.runSuitesLocally(TestNG.java:964)
        at org.testng.TestNG.run(TestNG.java:900)
        at org.apache.maven.surefire.testng.TestNGExecutor.run(TestNGExecutor.java:70)
        at org.apache.maven.surefire.testng.TestNGDirectoryTestSuite.executeMulti(TestNGDirectoryTestSuite.java:149)
        at org.apache.maven.surefire.testng.TestNGDirectoryTestSuite.execute(TestNGDirectoryTestSuite.java:95)
        at org.apache.maven.surefire.testng.TestNGProvider.invoke(TestNGProvider.java:114)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at org.apache.maven.surefire.booter.ProviderFactory$ClassLoaderProxy.invoke(ProviderFactory.java:103)
        at $Proxy0.invoke(Unknown Source)
        at org.apache.maven.surefire.booter.SurefireStarter.invokeProvider(SurefireStarter.java:150)
        at org.apache.maven.surefire.booter.SurefireStarter.runSuitesInProcess(SurefireStarter.java:91)
        at org.apache.maven.surefire.booter.ForkedBooter.main(ForkedBooter.java:69)
Caused by: java.lang.UnsatisfiedLinkError: no snappyjava in java.library.path
        at java.lang.ClassLoader.loadLibrary(ClassLoader.java:1738)
        at java.lang.Runtime.loadLibrary0(Runtime.java:823)
        at java.lang.System.loadLibrary(System.java:1028)
        at org.xerial.snappy.SnappyNativeLoader.loadLibrary(SnappyNativeLoader.java:52)
        ... 45 more
Tests run: 22, Failures: 2, Errors: 0, Skipped: 0, Time elapsed: 6.292 sec <<< FAILURE!

Results :

Failed tests:
  testByteForByteOutputSyntheticData(org.iq80.snappy.SnappyTest): 1 byte block
  testByteForByteTestData(org.iq80.snappy.SnappyTest): Testdata: alice29.txt

Tests run: 22, Failures: 2, Errors: 0, Skipped: 0

[INFO] ------------------------------------------------------------------------
[INFO] BUILD FAILURE
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 8.846s
[INFO] Finished at: Mon Apr 01 15:00:35 EDT 2013
[INFO] Final Memory: 6M/244M
[INFO] ------------------------------------------------------------------------
[ERROR] Failed to execute goal org.apache.maven.plugins:maven-surefire-plugin:2.8.1:test (default-test) on project snappy: There are test failu
[ERROR]
[ERROR] Please refer to o:\java\snappy-0.3\target\surefire-reports for the individual test results.
[ERROR] -> [Help 1]
[ERROR]
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR]
[ERROR] For more information about the errors and possible solutions, please read the following articles:
[ERROR] [Help 1] http://cwiki.apache.org/confluence/display/MAVEN/MojoFailureException
o:\java\snappy-0.3>

As far as I can see the reason is that mvn package did not build the jar file. I have downloaded the version tagged 0.3 (https://github.com/dain/snappy/archive/snappy-0.3.tar.gz)
What am I doing wrong?
Thank you.

Is the dependency on Hadoop core necessary?

Resolving the maven dependency for the Hadoop core brings in a lot of stuff. Is it all necessary?

OpenJDK compatablity

Hello, running the following JVM:
java version "1.6.0_27"
OpenJDK Runtime Environment (IcedTea6 1.12.6) (6b27-1.12.6-1ubuntu0.12.04.2)
OpenJDK 64-Bit Server VM (build 20.0-b12, mixed mode)

I get the following compiler warnings:

src/main/java/org/iq80/snappy/UnsafeMemory.java:26: warning: sun.misc.Unsafe is internal proprietary API and may be removed in a future release
private static final Unsafe unsafe;

src/main/java/org/iq80/snappy/UnsafeMemory.java:30: warning: sun.misc.Unsafe is internal proprietary API and may be removed in a future release
Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");

src/main/java/org/iq80/snappy/UnsafeMemory.java:32: warning: sun.misc.Unsafe is internal proprietary API and may be removed in a future release
unsafe = (Unsafe) theUnsafe.get(null);

src/main/java/org/iq80/snappy/UnsafeMemory.java:101: copyMemory(long,long,long) in sun.misc.Unsafe cannot be applied to (byte[],long,byte[],long,int)
unsafe.copyMemory(input, UnsafeMemory.BYTE_ARRAY_OFFSET + inputIndex, output, UnsafeMemory.BYTE_ARRAY_OFFSET + outputIndex, length);

Does not work with SequenceFile

Hi,

the codec does not work with the SequenceFile format, which is one of the most widely used file formats in Hadoop. That's a pity because I like the idea of not having to link a native library.

That being said, I forked your repo and will commit the changes that are necessary in order to make it work for SequenceFile. I can also provide a test case that shows that it is working for SequenceFile.

Sadly, your regression is failing because I disabled the following two things:

No more guessing on when the input stream finishes. (eof flag)
The stream header does not work in the context of Hadoop. I looked into the native implementation of Snappy and could not find where they are doing that. Is this really required?

Can you please comment on that and let me know what would be your take on that?

Cheers,
Sebastian.

snappy 1.1

The documentation page states "This compression code produces a byte-for-byte exact copy of the output created by the original C++ code..." That appears to be accurate for the 1.0.4 version of snappy. There are differences, however, with the 1.1 version of snappy. This can be seen by comparing output from snappy-java 1.1 or newer (1.1.1 is what I used).

It appears that the most significant change is google/snappy@27a0cc3, where the block size was changed from 32k to 64k.

Commons Compress

Have you considered contributing this code to the Apache Commons Compress library?

snappy-framed implementation

Has any thought been given to providing a x-snappy-framed implementation[1]?

I would be willing to provide an implementation if there is interest.

http://code.google.com/p/snappy/source/browse/trunk/format_description.txt

Exception in Snappy.determineSnappyInputStream

in version 0.4, Snappy.Java line 62.

if (read != STREAM_HEADER.length || read != HEADER_BYTES.length) {
throw new IllegalArgumentException("invalid header");
}

Is the logic valid? The condition will always be false so I always get an exception.

Should it be:

if (read != STREAM_HEADER.length && read != HEADER_BYTES.length) {
throw new IllegalArgumentException("invalid header");
}

Method Snappy.compress(byte[] data) should be static

It seems that method Snappy.compress(byte[] data) is supposed to be static as all the methods in the class Snappy, but it isn't. Could you please change that?

SnappyInputStream.read(int) is broken

SnappyInputStream.read(int) is broken. You should definitely modify your test suite (verification tests) to exercise read(int) as well as read(byte[]).

This method is required to return positive values between 0-255 (except for -1 which indicates end of stream), but returns negative values instead. The method currently returns "buffer[position++]" when it should return "buffer[position++] & 0xff".

EXCEPTION_ACCESS_VIOLATION uncompressing data

Affects 0.5-SNAPSHOT (dfb88c3)
Call org.iq80.snappy.Snappy#uncompress(byte[], int, int) using these parameters:

compressed = [107,115,47,85,112,-127,83,30,49,9,0,67,38,-99,41,9,25,26,102,20,81,116,-2,8,21,98,8,21,-18,-94,0,5,-94,41,69,-2,60,22,98,60,22,-50,-96,0,109,-88,0,-111,-2,-42,1,-2,-42,1,61,-42,41,38,12,-61,4,0,-110,-70,-107,0,98,-36,2,28,114,101,115,117,108,116,47,82,5,7,101,-75,18,-91,17,12,72,101,97,100,26,-39,44,102,27,0,54,-76,5,-2,-48,4,-107,-48,-126,-109,0,41,6,8,-23,3,0,-58,-77,4,117,-12,62,18,0,4,118,21,66,18,0,0,29,66,18,0,0,33,62,18,0,4,117,-34,62,18,0,4,118,24,62,18,0,4,117,-20,62,18,0,4,118,64,66,18,0,0,0,54,18,0,12,-3,1,-59,82,54,18,0,12,-74,8,117,-14,62,18,0,4,118,4,62,18,0,4,117,-31,62,18,0,4,118,2,62,18,0,4,117,-51,66,18,0,0,-40,66,18,0,0,-1,62,18,0,4,118,51,62,18,0,4,117,-7,62,18,0,4,118,53,66,18,0,0,22,62,18,0,4,117,-27,54,18,0,12,-3,1,-59,80,50,18,0,16,80,-114,-7,110,-113,50,18,0,65,-30,0,34,62,18,0,4,117,-52,62,18,0,70,10,2,4,118,20,66,36,0,0,46,62,18,0,4,117,-25,66,18,0,0,-5,62,18,0,4,118,41,66,18,0,70,-66,2,0,58,66,36,0,0,8,62,18,0,4,117,-33,62,18,0,4,118,16,62,18,0,4,117,-15,66,18,0,0,-55,66,18,0,0,-44,62,18,0,4,118,45,62,18,0,4,117,-22,62,18,0,4,118,25,66,18,0,0,27,66,18,0,0,10,62,18,0,4,117,-49,66,18,0,0,-23,66,18,0,0,-19,62,18,0,4,118,50,66,18,0,0,55,62,18,0,4,117,-13,66,18,0,0,-21,62,18,0,4,118,39,62,18,0,70,118,2,4,117,-36,50,36,0,65,64,0,-110,50,18,0,97,60,0,-45,62,18,0,4,118,32,50,18,0,1,54,0,-112,50,18,0,1,54,0,-50,62,18,0,4,118,44,62,18,0,4,117,-48,17,18,4,25,97,-83,-114,0,107,54,18,0,12,-3,1,-59,89,54,18,0,12,-74,8,118,94,66,18,0,0,81,66,18,0,0,102,66,18,0,0,79,66,18,0,0,68,66,18,0,0,88,54,18,0,12,-3,1,-59,85,54,18,0,12,-74,8,118,78,66,18,0,58,54,0,12,-74,8,118,70,66,36,0,58,72,0,12,-3,1,-59,87,66,36,0,0,111,66,18,0,0,103,66,18,0,70,54,0,0,92,66,36,0,0,73,66,18,0,0,90,66,18,0,70,90,0,0,114,66,36,0,0,106,66,18,0,0,104,66,18,0,0,86,66,18,0,0,100,66,18,0,0,109,66,18,0,0,98,66,18,0,0,75,66,18,0,0,69,66,18,0,0,72,66,18,0,-75,-24,85,64,0,101,66,36,0,0,74,66,18,0,0,96,66,18,0,0,93,66,18,0,-75,88,5,90,65,-30,0,-108,66,36,0,0,71,66,18,0,0,105,66,18,0,0,91,66,18,0,0,108,66,18,0,0,76,66,18,0,0,97,66,18,0,0,84,66,18,0,0,99,17,18,4,23,24,105,60,4,89,112,66,18,0,0,49,66,18,0,53,-98,21,54,-103,-2,17,72,117,114,21,18,70,108,0,0,-126,21,90,32,27,0,0,1,79,64,-41,-21,-54,21,18,17,72,53,104,5,36,12,78,-74,8,98,25,18,17,36,53,122,5,18,16,80,-109,-55,1,56,66,72,0,0,95,66,18,0,0,61,66,18,0,53,104,5,72,12,78,-74,8,89,53,50,21,18,53,86,21,18,-71,88,17,-112,0,-123,66,90,0,0,-127,66,18,0,0,116,50,18,0,12,80,101,-3,-122,57,14,17,72,0,126,21,36,49,32,-7,116,17,36,-107,56,21,36,-39,120,17,36,0,127,66,72,0,0,-24,21,18,17,36,0,125,21,18,1,108,33,104,0,63,21,18,17,36,-7,98,1,36,33,-80,0,-62,50,36,0,16,80,-114,-7,105,-119,21,18,17,36,0,120,21,18,17,72,0,-128,21,18,17,36,38,50,10,17,36,0,52,50,36,0,1,-112,85,-30,21,36,-107,56,21,72,0,-31,21,54,17,72,0,50,21,18,17,108,0,-107,21,18,17,36,0,98,21,18,1,36,16,80,-114,-7,107,57,21,18,17,36,0,113,66,18,0,0,67,21,18,1,54,12,78,-74,8,97,25,-58,1,18,33,32,0,-81,21,36,17,72,-107,-56,9,18,12,-3,1,-67,30,21,36,17,54,0,-95,50,18,0,1,90,70,-44,1,38,72,9,5,90,8,-3,1,-67,38,-124,12,17,72,-11,26,9,36,12,-74,8,89,47,50,90,0,1,-94,0,64,66,18,0,-7,-68,5,90,8,-74,8,89,-75,-78,21,18,-7,-122,1,108,33,50,38,-34,12,17,54,0,119,66,90,0,0,-56,21,18,17,36,54,-26,1,1,-112,38,76,8,17,36,0,118,21,54,1,108,65,10,38,-52,12,17,36,-43,120,5,36,1,72,70,-52,3,-75,-60,21,36,0,-46,21,90,17,72,25,54,17,108,-43,84,5,18,1,90,0,-83,66,54,0,-11,-86,21,72,0,65,21,36,13,72,0,97,38,-84,11,17,108,34,94,8,21,36,70,-80,1,54,126,0,65,10,0,-69,21,90,17,72,0,69,21,18,17,108,38,-98,10,1,18,1,-76,54,52,5,-95,34,70,-2,4,0,66,62,72,0,0,98,38,64,11,17,108,-11,26,21,90,38,-70,12,17,108,70,66,6,89,100,17,72,0,115,66,108,0,38,-38,13,17,36,-43,-28,21,90,34,-108,8,5,18,65,10,-11,-50,21,54,0,121,66,90,0,34,-126,8,21,36,121,-52,17,-76,0,124,21,54,17,126,0,-124,66,18,0,0,123,21,18,17,54,0,62,21,18,5,54,12,-3,1,-67,28,54,18,0,8,-74,8,89,34,108,9,5,54,33,-62,0,-35,66,36,0,70,-60,5,-71,-6,5,90,8,-74,8,89,34,-80,10,21,72,0,-41,66,72,0,0,83,21,18,17,-94,-71,106,1,72,12,79,64,-41,-22,54,-30,2,65,28,0,-32,21,54,1,36,1,108,0,-125,21,18,1,72,1,-76,38,-120,11,17,36,-103,20,13,36,0,98,38,120,15,17,36,34,-54,8,5,36,1,108,25,90,1,36,-63,-10,70,-100,6,0,60,21,126,1,36,1,-112,0,117,21,18,1,108,1,72,0,-71,21,18,17,36,-7,-104,1,36,-127,-110,54,4,8,65,-12,25,90,1,36,1,-40,38,92,13,17,72,25,54,17,36,0,-66,66,108,0,34,42,12,5,36,1,-112,0,-92,66,36,0,57,-62,17,72,38,-10,15,17,108,34,6,12,5,36,1,72,38,-100,15,17,36,70,-44,1,54,8,7,1,-40,54,-104,7,1,-40,38,36,18,17,72,-7,-50,1,-112,1,108,38,22,17,17,36,54,100,2,1,36,0,-98,66,-40,0,38,90,18,17,72,0,-60,66,36,0,0,122,21,18,1,36,1,-112,0,-10,21,18,17,108,0,110,21,18,1,36,1,108,0,-87,21,18,17,36,34,114,12,5,36,1,72,54,-78,5,65,-48,70,32,1,0,-116,66,72,0,34,20,13,17,72,0,98,25,126,17,108,38,-90,8,1,-112,-127,92,0,26,50,72,0,1,108,58,-8,10,8,-3,1,-67,25,36,17,54,89,100,17,90,34,-74,13,21,36,-7,62,17,36,34,70,14,17,36,0,97,38,-28,15,17,36,-103,-92,13,108,4,97,-70,21,-94,17,18,70,-114,5,0,-121,50,36,0,33,104,70,78,3,-39,84,1,72,1,36,38,-118,15,1,18,33,122,0,-43,66,72,0,38,40,17,1,36,1,54,0,-64,66,36,0,38,-98,19,1,36,33,86,34,52,14,17,18,4,97,-67,50,54,0,1,108,0,-68,66,18,0,38,22,8,1,72,1,108,70,-118,6,0,-100,50,54,0,1,36,0,-58,50,18,0,1,126,70,-30,2,54,-98,1,1,54,70,120,6,0,-105,62,72,0,4,97,-2,50,18,0,1,54,54,-24,5,1,18,0,-26,50,36,0,1,126,54,50,10,1,36,70,18,0,89,-102,1,-22,33,14,70,-44,1,70,100,11,0,-17,50,108,0,1,90,0,-114,50,18,0,1,126,54,-6,5,1,18,38,92,22,1,108,1,54,70,-70,3,0,-39,66,72,0,0,40,62,18,0,4,97,-53,66,18,0,38,-56,22,1,90,1,108,-103,-74,1,18,1,108,0,-79,50,54,0,1,18,0,-77,66,18,0,70,-34,3,0,-75,66,36,0,54,82,2,1,72,-39,-82,1,108,33,68,38,126,18,1,18,1,36,70,124,5,54,-82,6,-63,66,38,-38,13,17,54,70,-72,8,38,-92,22,17,36,0,-85,66,-94,0,38,104,19,17,36,38,34,14,17,18,0,-73,66,54,0,34,26,16,5,36,33,68,38,110,22,1,54,1,18,70,-44,10,38,-24,14,1,36,1,-22,0,-90,66,90,0,0,-29,66,18,0,54,-124,3,1,54,0,-42,50,36,0,33,68,66,18,0,42,-120,11,1,108,1,-112,0,7,62,54,0,0,98,-71,52,13,36,0,97,54,20,4,1,108,70,42,12,54,54,0,1,36,38,80,16,1,72,1,18,34,94,17,21,18,54,10,11,1,36,54,-38,13,1,-58,0,-47,66,-94,0,0,59,62,18,0,0,97,38,94,8,17,108,38,82,11,12,20,0,0,1,14,122,19,121,-124,5,18,8,-74,8,123,25,-40,17,18,-103,-110,17,18,0,-117,21,108,17,18,38,0,9,1,18,12,80,-119,60,-9,54,18,0,1,90,-71,-60,1,36,1,126,0,-103,54,72,0,12,-3,1,-59,-120,50,18,0,14,108,18,38,-20,22,5,54,12,-74,8,123,-88,54,36,0,8,-109,-56,-28,38,30,15,1,36,1,54,0,-30,50,36,0,1,54,-39,12,1,36,1,108,-103,92,5,18,8,-74,8,123,38,-44,10,17,18,-71,52,1,18,1,90,38,-24,23,1,18,1,54,121,-88,5,18,8,-3,1,-59,38,-80,10,17,18,54,72,0,16,79,64,-45,-117,-93,54,-94,0,8,-3,1,-59,38,108,9,17,54,-7,44,5,18,8,-74,8,123,57,-8,1,18,1,-112,38,108,9,1,18,1,72,38,-126,17,5,18,8,-74,8,123,-39,120,5,18,8,-3,1,-59,70,-62,1,38,-72,8,17,36,38,62,25,17,18,38,78,12,5,18,12,-74,8,123,-99,66,-58,0,70,126,0,0,-118,50,36,0,1,-76,38,22,8,17,72,70,90,0,0,-106,50,54,0,1,108,0,-61,66,18,0,38,-98,28,17,72,38,78,12,17,18,70,-116,1,38,36,18,17,36,58,24,3,8,-74,8,123,54,-94,0,65,100,38,-108,26,17,54,38,-90,17,17,18,0,-28,66,-94,0,38,-94,18,17,36,0,-101,50,36,0,1,90,38,18,27,5,36,12,-3,1,-59,-122,50,36,0,1,-112,70,42,3,0,-109,66,36,0,58,10,2,8,-74,8,123,38,4,17,5,90,8,-74,8,123,38,0,9,17,18,-39,-28,1,18,12,79,64,-41,-13,34,30,24,5,18,1,54,38,92,13,1,36,1,18,54,-88,3,1,18,38,22,17,17,36,0,-104,66,-94,0,0,-59,50,18,0,65,10,70,68,1,38,-120,11,1,72,14,24,12,58,28,2,8,-3,1,-59,58,-40,0,8,-3,1,-59,34,-110,22,5,54,1,-58,38,-12,20,1,72,1,-94,0,-74,50,126,0,1,18,38,10,29,1,36,12,80,101,-3,-121,38,38,22,1,18,1,36,38,14,19,17,18,70,-110,4,-7,-14,17,36,38,112,8,17,18,38,20,22,5,18,8,-3,1,-59,38,-30,11,1,18,1,-76,38,-66,11,1,18,12,80,-114,-7,111,58,-74,4,8,-74,8,124,54,20,4,33,68,38,54,9,1,54,1,36,-39,120,17,18,38,-44,10,1,18,1,108,58,-88,3,8,-3,1,-58,38,58,17,1,36,1,72,38,40,8,1,18,1,54,38,126,9,17,18,38,40,17,1,18,1,-40,38,-80,10,5,18,8,-74,8,124,38,-84,20,13,18,0,125,38,78,30,5,18,8,-3,1,-58,34,-64,24,5,18,1,-4,-7,26,5,36,8,-74,8,124,38,54,9,17,18,38,104,28,5,18,8,-3,1,-58,38,82,29,1,18,1,72,38,-40,18,17,18,54,-58,0,12,78,-74,8,125,38,-56,22,17,36,38,-34,12,17,18,38,-4,9,1,18,1,54,54,90,0,1,126,38,70,32,13,36,0,124,54,88,5,1,-112,38,28,11,5,36,8,-3,1,-58,38,36,9,5,18,8,-74,8,124,54,-112,0,33,122,38,42,12,13,36,0,125,38,110,13,1,18,-127,74,0,56,50,-30,2,1,108,38,-112,18,1,36,1,90,58,110,4,8,-74,8,124,54,-24,5,1,54,38,-44,28,13,54,0,125,38,-100,33,1,18,1,36,0,17,50,108,0,33,14,58,118,2,8,-3,1,-58,38,20,22,17,54,66,56,4,0,124,38,30,15,1,36,1,-112,38,86,10,13,18,0,125,38,-62,10,1,18,1,126,38,-30,11,1,18,1,54,38,-68,16,17,18,66,34,5,0,124,38,-34,12,17,36,0,-8,66,-58,0,38,26,16,5,36,8,-3,1,-58,38,100,20,5,18,12,-74,8,124,-63,66,54,0,38,-44,10,17,36,58,116,7,8,-74,8,123,38,40,35,13,36,0,125,38,-22,9,13,18,0,124,38,126,18,17,18,38,-4,9,5,18,8,-3,1,-58,38,78,21,5,18,8,-74,8,125,38,-128,13,13,18,0,124,38,-110,22,17,18,38,60,21,13,18,0,125,54,-30,2,1,-40,58,22,8,8,-3,1,-59,38,94,17,5,54,8,-3,1,-58,66,108,0,0,125,54,-102,2,33,-98,38,80,16,1,54,1,18,38,-84,20,1,18,1,108,66,64,2,0,124,38,-102,11,13,36,0,125,70,-48,2,0,19,50,122,1,1,90,38,-58,18,17,54,66,-88,3,0,124,54,58,8,14,126,9,38,-118,24,1,54,1,72,54,68,10,1,-22,38,-42,32,1,36,33,104,0,42,50,126,0,1,-58,70,68,1,38,88,14,13,54,4,124,23,62,54,0,0,125,66,112,8,0,125,38,-50,16,17,54,70,-70,3,38,-28,15,1,36,1,-76,70,-112,0,38,-70,21,1,36,1,-94,70,-20,4,54,4,8,1,72,38,62,34,13,54,0,125,38,-52,12,1,18,1,36,38,34,14,17,18,38,94,26,1,18,33,32,70,126,0,54,78,3,-31,98,38,-88,12,13,54,4,123,-6,62,32,1,0,124,70,-8,1,38,-44,37,1,54,1,-112,0,78,62,54,0,0,125,54,104,1,12,79,110,-3,-69,66,-30,11,0,124,54,-84,11,1,72,38,-44,37,1,90,1,-58,38,16,23,1,18,1,36,0,7,66,108,0,38,18,36,17,36,38,-28,15,1,18,65,100,38,-50,34,1,18,33,-116,54,-4,9,1,-94,0,-97,62,90,0,0,124,58,28,2,12,-3,1,-58,43,54,36,0,8,-3,1,-59,66,118,11,0,-58,70,-120,2,70,50,1,54,124,5,1,-40,54,124,5,1,18,70,4,8,38,-58,27,5,-58,8,-3,1,-58,66,118,2,0,125,54,-40,9,1,36,54,14,1,33,86,38,-112,18,5,72,4,-74,8,62,124,5,8,-3,1,-59,38,-88,21,17,36,0,-115,54,-4,0,8,-74,8,124,66,-2,4,0,124,54,20,13,1,36,54,68,10,1,-112,38,92,22,17,90,70,-98,1,38,14,19,17,36,54,-96,5,33,32,58,-86,7,8,-3,1,-59,58,72,0,8,-3,1,-58,54,-104,7,1,-112,38,-30,20,17,90,38,-88,39,5,18,8,-3,1,-58,58,100,2,66,72,0,14,4,8,54,-82,15,1,-112,70,-68,7,34,54,36,9,90,8,-74,8,125,66,52,5,0,110,66,114,3,0,125,38,-8,28,1,-112,14,76,8,58,50,1,8,-3,1,-59,58,-62,10,8,-74,8,124,38,12,33,1,54,1,-76,0,13,66,-80,1,58,-24,14,12,-74,8,125,-96,54,36,0,8,-3,1,-59,38,16,32,5,72,8,-74,8,124,54,2,13,1,-112,38,126,27,17,36,0,-48,62,72,0,0,-58,38,96,39,1,36,97,96,54,24,12,1,90,0,21,50,54,0,1,90,54,-26,1,1,-94,38,-58,18,1,72,1,18,38,86,19,1,18,1,54,54,50,1,1,90,38,-94,18,1,36,1,18,66,66,6,0,124,70,32,10,58,90,0,8,-114,-7,111,66,-112,0,0,124,38,42,30,17,90,58,16,14,12,-74,8,124,-86,50,-40,0,33,-116,58,-112,9,8,-74,8,125,66,-78,5,0,124,70,44,7,58,-90,17,4,-74,8,74,-36,8,0,-72,50,108,0,14,-124,12,54,74,13,1,-112,54,60,12,1,-40,54,52,5,14,18,9,58,114,3,8,-3,1,-59,54,-52,12,65,-12,54,2,13,1,72,54,86,10,1,-94,54,20,4,33,-98,54,102,6,1,72,38,122,19,49,68,70,-76,0,54,100,2,1,108,54,124,5,1,18,54,88,14,1,18,38,96,30,1,90,12,79,95,86,-76,38,122,19,1,18,33,14,58,-18,8,8,-3,1,-58,54,-22,9,1,72,38,34,32,5,54,8,-3,1,-59,54,-86,7,1,-22,54,-66,11,-63,102,38,-64,24,5,54,8,-74,8,125,54,-98,1,1,18,58,126,0,8,-74,8,124,38,8,43,13,54,0,124,58,-110,13,12,-74,8,125,1,50,-26,1,1,-112,54,44,16,1,36,0,9,54,36,0,8,-74,8,125,38,-34,30,17,90,66,-8,1,62,2,4,0,-74,62,10,11,33,14,38,20,22,1,72,1,18,70,34,14,54,-14,7,1,-40,38,-26,28,1,54,33,104,38,-54,26,5,18,8,-74,8,125,66,36,0,0,-59,38,-42,32,5,36,8,-3,1,-58,58,-38,13,8,-74,8,124,34,92,40,5,36,14,-104,16,54,42,3,97,6,54,78,12,1,-76,54,-70,12,1,90,66,-80,10,62,98,7,8,-74,8,123,38,58,44,17,-112,54,-4,9,1,-112,58,-118,6,8,-74,8,125,58,102,6,8,-3,1,-58,38,46,29,5,72,12,-74,8,124,-97,54,-80,1,8,-3,1,-58,70,-18,8,0,15,54,36,0,8,-74,8,124,38,-96,32,1,72,1,-40,0,-111,66,36,0,38,8,34,1,36,1,-112,58,82,11,8,-74,8,125,54,-106,3,1,18,70,104,10,54,-14,7,1,108,38,-68,43,1,90,1,18,38,-128,31,17,18,58,-26,19,8,-74,8,125,70,52,5,70,-128,13,54,-76,0,97,78,38,36,45,1,90,1,-4,70,44,7,38,-120,29,13,36,0,123,38,-88,30,5,18,8,-3,1,-59,38,76,26,5,18,8,-74,8,124,70,84,15,58,-82,6,8,64,-45,-117,66,104,19,0,125,54,56,13,1,-4,54,120,6,1,54,0,-84,66,-116,1,0,38,50,18,0,1,36,66,-58,0,0,124,54,22,8,33,50,54,-94,0,1,108,54,-38,13,1,-40,54,-6,14,1,36,54,78,21,1,18,66,106,14,0,124,38,-30,38,33,14,97,42,38,56,49,1,18,33,32,54,-40,0,1,18,70,-40,0,0,-80,50,-40,0,1,36,54,8,16,1,90,54,-26,1,1,-112,38,-74,40,17,108,54,92,22,1,36,70,-28,15,58,124,5,8,-3,1,-58,54,-52,12,1,126,58,-62,19,12,110,-3,-69,-102,66,-94,0,54,32,19,1,36,54,12,24,1,90,70,24,3,38,100,47,13,-76,4,125,-65,50,90,0,1,-76,54,124,5,1,18,70,76,8,70,-114,5,54,-56,13,33,-8,38,78,39,1,108,14,-92,13,54,56,4,33,86,0,-3,66,126,0,0,36,50,18,0,33,14,70,-58,9,70,126,9,54,-124,21,33,14,70,-54,8,66,-114,14,0,124,38,-96,41,1,-94,1,108,38,66,33,17,18,54,-8,19,1,-40,66,-126,17,0,125,38,-48,38,17,54,54,92,4,33,-116,54,56,13,1,72,54,100,20,33,104,58,-68,7,8,-109,-55,1,70,92,13,66,-58,18,0,124,70,22,17,70,44,16,54,-8,1,1,108,70,122,19,38,-76,36,17,-58,54,-42,14,97,-88,58,-110,13,8,-74,8,125,54,20,4,1,18,70,-36,8,58,-64,15,8,-3,1,-58,54,72,18,1,-112,54,64,11,1,36,54,54,9,1,18,38,-96,32,13,-94,0,125,38,-40,36,1,18,1,72,0,77,50,64,2,1,18,58,-94,0,8,-3,1,-59,54,-22,27,14,-58,9,54,82,2,14,-22,9,58,-32,7,8,-3,1,-58,54,56,22,1,90,66,-42,23,0,124,54,-38,4,65,-12,66,28,11,0,125,38,-114,41,17,-76,66,120,24,0,-58,66,72,9,58,42,12,65,-84,0,-96,66,-22,0,38,-78,32,17,90,38,-4,45,5,18,8,-124,-97,25,70,8,7,58,-30,2,8,-3,1,-59,54,-40,18,1,108,38,40,53,5,72,4,-114,-7,62,-88,3,8,-3,1,-58,38,-26,46,17,36,58,64,11,8,-114,-7,111,54,-118,24,1,90,54,-66,2,65,64,0,46,50,-40,0,1,36,54,6,3,1,18,54,-2,4,-127,74,38,18,54,5,126,8,-109,-56,-28,54,110,4,1,54,66,108,27,0,124,38,22,44,1,54,65,10,70,-60,5,54,-112,9,-127,92,54,-70,30,1,-40,38,-92,40,1,72,1,-58,0,-57,50,-58,0,1,36,66,114,21,0,-59,54,-58,27,1,36,0,11,50,54,0,1,-76,66,54,0,4,-58,12,50,36,0,1,-76,54,48,6,33,-116,54,6,3,12,79,64,-45,-116,54,-26,1,1,108,54,0,27,1,18,54,80,7,1,72,58,0,18,8,-3,1,-58,54,-42,5,1,-94,70,-112,0,54,102,15,33,14,66,106,5,0,125,66,82,29,0,124,66,-20,22,58,-96,23,1,108,70,-120,2,54,108,0,1,-58,54,14,1,1,18,54,-26,10,1,18,66,48,15,0,125,66,-92,31,74,46,20,54,62,25,1,72,58,-52,12,8,-74,8,124,54,-124,3,33,50,66,-38,13,0,110,58,96,30,8,-3,1,-58,58,-48,11,8,-74,8,124,66,40,17,58,96,3,1,36,66,-114,32,0,124,54,-20,13,1,-94,66,78,3,0,125,54,36,0,33,-98,54,-20,4,65,82,70,-30,20,66,56,22,0,125,54,78,3,1,108,54,-110,31,1,72,54,-128,22,97,60,58,-66,29,8,-3,1,-59,66,80,7,0,124,58,-54,8,8,-74,8,125,38,24,48,109,96,0,124,54,78,12,1,126,58,-24,32,82,-78,14,58,98,7,8,-114,-7,111,54,-4,0,33,-116,66,-110,4,0,124,54,-52,21,12,79,69,-30,55,54,-60,5,33,-116,66,-112,18,0,124,58,-22,0,12,-74,8,124,-5,50,-70,3,1,-94,58,126,0,0,-74,78,-12,20,66,80,7,0,110,54,28,20,1,-58,54,-66,29,1,72,54,-18,8,1,36,38,10,38,49,68,38,122,37,17,18,58,98,7,8,-3,1,-59,38,4,44,1,36,14,-12,11,54,94,17,-95,106,54,-68,25,1,108,70,-64,6,58,24,3,8,-74,8,124,54,-56,13,65,28,54,118,20,1,36,38,80,61,1,126,33,-98,54,2,22,1,108,58,42,3,8,-74,8,124,54,-120,2,33,14,58,24,21,4,-74,8,58,-74,4,-31,-86,70,-116,1,70,74,4,70,32,1,54,64,11,1,90,38,2,49,1,-76,33,32,70,-2,22,58,72,9,8,-3,1,-58,54,-126,17,1,18,54,118,11,1,18,54,18,9,-63,-10,38,58,44,5,108,8,-114,-7,111,66,26,7,0,111,38,-102,47,1,36,1,-94,58,102,6,8,-3,1,-59,70,10,2,70,50,1,54,-18,8,1,108,54,126,9,1,90,38,60,39,13,108,0,125,54,-78,5,33,-116,70,-104,7,54,80,7,1,72,38,26,52,13,72,0,124,54,-110,4,1,126,66,-120,20,58,-8,1,14,50,19,0,-76,62,114,3,0,123,54,114,12,1,108,58,-8,10,8,-3,1,-58,54,54,9,1,36,58,-116,19,8,64,-41,-13,70,110,31,58,106,14,8,-3,1,-58,66,36,27,0,124,54,90,0,1,-58,58,-2,13,8,-3,1,-58,58,82,20,8,-3,1,-59,70,-22,9,70,68,1,54,82,29,1,90,54,-106,3,33,122,54,4,8,1,108,54,-40,0,1,-22,54,24,12,1,18,0,-82,50,68,1,1,90,70,-124,21,54,-4,9,1,108,25,18,0,30,22,-66,56,0,-22,38,84,15,17,18,38,66,15,17,18,38,-10,15,17,18,89,-66,1,18,14,68,55,38,46,11,17,18,38,54,18,1,18,-95,-96,38,-126,26,5,18,8,64,-41,-22,-39,30,1,18,1,72,38,2,22,1,18,14,-80,46,-103,-74,17,18,34,-114,14,4,25,99,14,-38,40,8,-74,8,89,34,32,10,21,18,-107,2,21,18,-107,-128,21,18,34,70,23,21,18,85,-30,21,18,53,104,21,18,0,-91,49,122,21,18,34,18,36,21,18,0,-95,66,36,0,34,-52,12,5,36,1,-22,34,-128,31,5,18,1,-58,-107,-92,21,18,34,-100,24,21,18,-75,-114,21,18,34,40,35,5,18,33,86,34,62,52,9,18,8,111,55,13,34,76,44,5,18,1,108,-11,8,21,18,34,54,36,5,18,1,54,34,108,27,5,18,1,54,34,78,21,21,18,34,-2,22,21,18,34,0,36,21,18,53,-44,21,18,85,28,21,18,34,-18,26,5,18,1,-58,117,-52,21,18,34,32,19,5,18,1,-112,-107,-128,21,18,0,-97,66,122,1,-107,110,5,36,33,122,34,110,13,21,18,-43,84,21,18,70,46,2,0,-99,66,90,0,34,-18,35,5,54,1,-112,34,-106,48,21,18,34,-90,44,21,18,70,118,2,70,-8,1,70,108,0,0,-78,66,126,0,34,-14,34,5,90,33,50,-75,52,5,18,70,-22,0,1,-94,0,-80,50,72,0,1,54,34,-126,8,5,54,1,36,34,94,35,21,18,54,54,0,1,36,34,-128,22,21,36,34,2,49,21,18,34,-100,24,21,18,54,-76,0,1,72,34,122,46,21,36,34,54,18,21,18,70,90,0,34,-40,9,21,36,54,-44,1,1,90,54,-44,1,1,18,-75,-78,21,54,34,-58,27,21,18,-107,-56,5,18,33,32,-11,-68,5,18,1,72,34,6,48,5,18,1,36,-75,124,9,18,8,95,86,-77,34,-6,14,5,18,1,54,38,-32,16,0,28,-119,-74,0,93,-39,12,17,18,21,126,17,18,0,94,38,-128,13,17,36,-39,12,17,18,54,54,0,12,80,-114,-7,106,38,126,9,13,36,0,92,38,-76,9,13,18,0,94,38,4,26,1,18,1,54,38,-58,18,1,18,1,-40,38,12,15,1,18,12,78,-74,8,93,-39,-82,5,18,8,-3,1,-67,38,-54,35,1,18,1,72,38,-78,14,17,18,38,-60,23,1,18,1,72,38,-66,11,13,18,0,92,38,80,25,1,18,1,72,38,32,19,17,18,38,-62,19,17,18,85,-102,5,18,1,-76,38,-70,12,17,36,38,-26,10,1,18,1,126,-75,-42,21,18,38,-66,11,13,36,0,94,38,-122,16,13,18,0,93,38,-14,43,17,18,38,72,9,1,18,1,126,38,48,42,1,18,1,108,38,94,44,1,18,1,36,38,22,8,1,18,12,78,-74,8,92,66,18,0,0,93,38,110,31,13,36,0,93,38,-84,20,17,18,38,94,26,1,18,33,50,38,-120,11,1,18,1,108,38,-100,24,1,18,1,-112,38,-44,55,1,18,1,36,38,6,48,9,18,4,-45,-122,38,66,15,1,18,1,54,38,-24,23,1,18,1,108,38,-60,14,1,18,1,72,54,-22,0,1,54,38,-28,24,1,36,14,118,11,38,-36,8,5,18,8,-114,-7,106,38,-104,25,17,18,38,-56,22,1,18,14,20,49,38,-50,16,1,18,1,90,38,58,35,5,18,8,-3,1,-67,66,-44,1,0,94,70,-98,1,38,68,19,5,54,8,-74,8,93,38,-86,16,1,18,1,-112,38,-104,16,1,18,1,36,38,-24,23,17,18,38,-54,26,1,18,1,54,38,16,14,1,18,1,54,54,-12,2,1,36,38,48,33,1,36,12,79,64,-45,-123,38,-126,26,1,18,1,54,54,-12,2,33,86,38,-104,16,17,36,-43,-100,5,18,1,90,-43,84,5,18,1,72,-107,-38,17,18,0,94,38,-100,15,17,72,38,-108,26,5,18,8,-3,1,-67,-107,-38,9,18,8,-74,8,92,38,46,29,5,36,8,-74,8,93,70,108,0,38,-6,32,17,36,54,56,4,1,-58,34,-126,8,5,36,1,-76,38,68,19,5,54,12,-3,1,-67,-89,-47,-100,9,18,8,-74,8,93,38,78,12,17,36,38,2,31,5,18,8,-74,8,93,34,-54,8,5,18,1,90,34,-58,9,21,18,34,50,10,5,18,12,78,-74,8,94,38,-118,15,17,72,54,-102,2,1,-112,38,-30,20,1,36,1,90,54,114,3,1,72,38,-16,30,17,36,66,124,5,0,93,38,8,16,1,36,1,-76,38,-64,15,13,18,0,92,38,2,13,13,18,0,93,70,14,1,70,6,3,66,118,2,0,94,38,68,19,17,72,38,46,20,17,18,38,-4,27,17,18,34,112,8,5,18,1,-22,38,112,17,17,36,38,94,17,13,18,0,92,70,-116,1,-11,-86,17,36,0,94,58,86,1,8,-74,8,93,38,-18,62,1,72,1,108,38,-106,12,17,18,34,-4,9,21,18,38,-74,13,17,36,58,122,1,8,-109,-56,-28,58,-30,2,8,-3,1,-67,54,30,6,12,80,111,85,-80,34,58,8,5,72,1,-112,54,-26,1,1,18,38,-88,48,17,108,0,126,66,-102,2,70,-24,5,-11,-14,5,54,1,72,54,-68,7,1,-94,38,-88,30,1,90,1,36,34,-84,11,17,18,74,-88,3,34,28,11,17,36,62,-2,4,8,-74,8,93,70,-94,0,70,8,7,38,18,45,1,126,1,-112,66,82,2,0,92,38,-108,35,5,36,8,-114,-7,106,38,-74,13,1,18,1,108,34,2,13,5,18,1,36,38,30,15,1,36,1,18,38,-72,35,17,18,70,-46,6,34,64,11,5,36,1,90,38,-68,34,17,54,38,-24,23,17,18,38,8,34,1,18,33,-26,54,-46,6,97,-106,38,-58,27,5,36,8,-74,8,93,38,-46,15,1,18,1,-94,38,-96,41,1,18,-127,-92,54,-20,4,1,36,38,-102,56,1,36,1,72,54,42,3,1,18,34,104,10,5,36,1,54,38,-126,17,17,54,70,46,2,34,-2,13,21,36,34,-88,12,90,18,0,33,-80,54,-40,0,1,108,38,86,28,1,108,1,18,38,-12,29,1,18,14,-62,19,58,-58,0,8,-3,1,-67,54,-128,4,12,79,100,-40,-100,54,44,7,1,72,34,-92,13,5,72,1,18,34,124,14,9,18,8,-109,-56,-28,70,-80,1,54,-128,4,1,54,34,12,15,5,54,33,50,54,-100,6,1,36,38,-116,19,1,-76,1,36,38,-118,60,17,18,54,10,2,1,36,38,-94,18,17,36,34,114,12,5,18,1,90,70,-24,5,54,-72,8,1,72,38,2,22,17,72,34,80,16,21,18,38,-46,42,13,36,58,-80,10,65,118,58,8,7,8,-3,1,-67,54,90,9,1,108,38,2,31,13,72,0,93,34,-78,14,21,18,38,12,33,1,36,1,-58,38,-62,28,1,18,-31,-104,54,98,7,1,90,38,-54,17,13,36,0,93,66,-10,6,0,93,34,-46,15,5,36,1,90,38,94,17,17,54,0,-126,66,-20,4,54,-64,6,97,42,58,72,0,8,-109,-56,-28,70,104,1,34,20,13,5,90,1,108,54,108,9,1,-76,34,30,15,5,36,1,90,38,-126,26,1,-112,1,54,54,12,6,1,54,38,20,22,17,36,54,-98,1,1,72,38,58,26,1,36,1,54,54,-106,3,1,90,38,100,38,1,36,1,-58,58,66,6,8,-74,8,92,54,12,6,1,72,38,20,58,5,54,8,-114,-7,106,54,72,9,1,126,38,80,34,1,36,65,10,54,92,13,1,18,34,-68,16,5,36,1,54,38,-54,44,5,54,8,-74,8,93,54,-16,12,1,18,34,-100,15,5,36,12,79,95,-101,-108,38,4,44,5,54,8,-3,1,-67,54,-94,0,1,54,54,86,1,1,36,0,-57,54,-26,1,8,-3,1,-67,38,6,30,5,72,8,-74,8,93,54,34,5,33,32,38,-92,22,17,36,34,-18,17,21,18,38,120,33,17,36,70,2,4,54,-94,9,1,108,54,6,12,1,18,54,72,9,33,104,70,66,15,38,-114,23,17,108,38,88,32,17,18,0,121,50,-22,0,1,72,54,78,3,1,18,0,-83,66,36,0,70,-94,0,54,-18,8,14,8,70,70,-40,0,38,60,21,5,126,8,-3,1,-67,70,-42,14,54,74,13,1,-22,70,122,1,70,-70,3,38,114,21,17,90,54,-124,3,1,72,38,38,49,5,36,8,-74,8,93,58,-120,2,8,-74,8,94,38,72,36,17,36,54,-48,11,33,14,54,-32,7,65,-102,0,-27,50,32,1,1,90,66,72,0,0,94,38,100,38,1,90,1,72,38,-88,39,1,18,1,54,70,-22,9,38,-64,24,17,36,70,54,0,38,-116,46,17,36,54,52,5,1,108,38,66,42,17,36,54,110,13,1,36,38,-8,28,17,36,34,38,22,5,18,1,36,38,0,27,1,36,14,124,14,58,-14,16,8,-74,8,93,34,50,19,5,36,1,54,54,-54,17,14,-38,13,38,92,31,1,72,1,54,66,-4,9,0,94,66,126,9,0,93,38,-26,46,1,54,33,122,38,-72,44,1,18,65,82,58,90,0,8,-3,1,-67,38,-124,57,1,36,1,-112,38,-72,26,1,18,1,126,54,22,8,1,36,66,80,16,58,18,18,1,90,38,4,44,17,72,38,106,32,17,18,54,100,11,1,108,34,38,22,17,36,58,-118,15,70,-120,2,33,104,70,124,5,38,74,31,5,108,8,-3,1,-67,54,32,1,1,72,70,-86,16,0,127,66,-84,2,0,111,50,18,0,33,86,58,72,0,8,-3,1,-67,54,-18,8,1,-58,38,126,27,5,126,4,-74,8,74,48,15,54,100,11,1,-112,38,-38,49,13,54,0,94,54,74,13,33,122,38,-16,30,17,36,54,-84,2,1,108,34,74,22,21,36,38,-116,37,13,54,0,93,54,94,8,12,79,105,-75,12,54,28,20,1,108,54,-86,16,1,90,38,-46,51,1,72,1,36,38,12,33,17,18,38,-108,53,1,18,-31,8,0,-10,50,68,1,1,54,38,-64,51,1,36,33,-62,66,-44,19,0,93,38,122,28,1,36,1,54,54,-120,11,1,-112,38,66,51,5,36,8,-109,-56,-28,54,74,4,33,-80,66,-120,2,0,94,54,-118,6,1,36,38,-108,62,1,72,1,90,70,8,7,70,28,2,38,-50,43,1,54,1,-94,54,74,13,1,18,38,-100,33,1,36,65,46,54,14,1,33,32,58,-88,3,8,-74,8,93,34,-10,24,9,54,8,-74,8,93,34,-128,22,5,18,1,90,38,50,28,5,90,8,-74,8,93,54,22,8,1,18,38,-48,92,17,36,58,-120,11,8,-114,-7,106,54,50,1,1,54,70,14,1,34,-90,26,21,72,66,-52,3,0,94,38,96,30,17,108,54,72,9,1,108,38,110,31,17,36,54,52,5,1,126,58,86,10,12,-3,1,-67,-21,66,64,2,54,70,5,-95,52,38,-88,57,17,90,54,116,7,1,90,34,-114,23,17,36,74,70,5,54,-128,22,65,28,70,-120,2,54,-26,10,12,80,106,-81,112,70,102,6,66,-52,3,0,93,34,-82,24,5,126,33,14,70,-124,12,54,-22,18,1,-76,38,14,73,17,-40,58,-60,5,8,-74,8,93,38,-28,42,1,36,14,102,42,54,-46,6,1,108,70,90,9,54,-42,23,1,36,54,12,24,1,90,54,64,11,14,-128,31,66,-118,6,0,92,38,50,46,1,126,1,54,54,20,4,33,68,58,78,3,8,-3,1,-67,70,-12,2,54,12,24,70,54,0,1,18,70,14,1,34,28,29,5,126,1,-58,54,-18,17,1,-112,38,-32,34,1,-94,1,36,66,32,19,74,-126,8,54,-124,3,1,54,66,-12,2,74,-20,13,38,6,66,5,108,66,-24,14,1,-112,38,14,37,1,36,1,18,54,-60,23,1,54,54,12,15,1,36,34,-62,28,21,54,38,60,66,17,72,54,-116,1,1,-76,70,16,14,54,-56,4,33,86,54,-66,2,1,54,54,102,15,1,126,54,-74,4,1,36,38,46,38,1,126,1,72,54,8,25,1,36,66,-22,9,0,93,54,-76,9,1,36,54,-62,1,1,108,70,-46,15,34,96,30,5,108,1,54,54,102,6,1,18,38,-118,33,1,-112,1,72,38,124,32,1,18,1,36,38,-90,44,17,18,70,2,22,54,-28,6,1,72,0,-68,50,-128,4,1,18,34,-70,30,5,72,65,-48,38,-88,48,1,90,1,36,38,-98,55,17,18,70,36,18,54,114,12,33,68,54,-112,18,1,-76,58,118,20,8,-3,1,-67,54,26,25,1,108,54,2,22,-127,2,38,-118,51,17,126,34,-26,28,5,18,-95,52,54,118,2,1,72,54,-36,17,1,108,54,-74,4,1,36,70,106,5,70,-118,24,34,78,30,5,108,65,-48,70,18,27,54,122,10,14,0,9,66,92,4,0,93,54,38,4,33,14,70,-128,22,66,126,9,0,92,54,-120,2,1,-76,58,68,1,8,-74,8,93,38,122,37,33,32,33,122,54,-94,27,1,108,70,116,7,34,-124,30,17,54,0,-21,70,86,19,38,0,54,1,90,1,108,70,2,13,54,66,15,1,126,54,86,1,1,126,70,72,18,54,94,26,14,70,14,0,-83,50,-102,2,1,72,58,-8,10,8,-74,8,93,54,-76,0,14,112,8,70,26,7,58,90,18,8,-3,1,-67,54,74,4,1,72,70,68,10,0,-126,50,126,0,1,36,54,-78,14,1,18,70,42,30,54,108,0,1,-22,54,-66,11,1,18,38,96,48,49,68,38,52,50,1,18,1,36,54,-100,24,65,100,70,116,7,38,-28,51,1,54,1,-112,54,50,1,65,118,70,-92,13,54,10,2,1,54,54,-38,22,1,18,70,60,21,38,-14,43,1,108,1,-94,70,82,11,66,68,1,0,94,38,-8,10,0,32,22,-38,31,0,119,38,-68,16,17,18,38,-124,30,17,18,38,-28,15,17,18,25,-112,17,18,38,-32,25,1,18,14,92,40,38,-116,28,17,18,-103,-2,5,18,8,-109,-55,1,57,-44,5,18,8,101,-3,-121,-103,-92,1,18,12,78,-74,8,119,-71,-6,17,18,121,-106,17,18,38,-84,11,17,18,-71,-78,0,33,9,-22,0,120,25,126,17,18,38,54,18,17,18,121,-70,17,18,-103,-92,17,18,-39,-82,17,18,38,-126,17,17,18,38,46,20,17,18,38,-94,54,17,18,38,30,51,17,18,38,20,22,17,18,38,-2,13,17,18,-7,-14,17,18,38,108,18,17,18,38,-76,9,17,18,-39,-46,17,18,38,-6,14,17,18,38,-28,24,17,18,38,-124,30,17,18,38,-20,13,17,18,38,-126,17,17,18,-39,-64,17,18,70,14,1,-103,-20,17,36,38,108,9,17,18,38,-14,16,17,18,38,-62,10,17,18,34,118,38,4,23,35,41,-26,4,117,57,-107,38,17,18,38,-124,21,17,18,89,100,17,18,0,59,50,54,0,65,-66,38,2,22,17,36,38,-110,58,17,18,38,-44,46,13,18,0,116,-7,116,13,18,0,117,121,96,1,18,1,90,38,96,21,1,18,14,-120,101,38,94,17,17,18,38,-106,12,17,18,121,-34,17,18,38,58,17,8,34,0,0,-123,-110,121,-124,1,18,12,78,-74,8,120,38,-18,17,17,18,38,-84,11,17,18,38,84,60,17,18,25,-76,17,18,38,-120,56,17,18,-103,-128,1,18,1,-40,34,14,37,9,18,8,-109,-56,-28,38,110,22,1,36,1,-112,38,-48,20,17,18,38,48,60,17,18,38,126,27,1,18,1,72,38,8,25,1,18,1,72,38,-96,50,17,18,38,-126,8,1,18,1,54,57,-26,1,18,1,54,38,94,26,17,18,38,54,9,17,18,38,56,31,17,18,38,-6,14,1,18,1,-22,-103,38,1,18,1,90,70,68,1,38,2,13,1,36,1,-112,38,34,23,1,18,1,54,38,80,16,17,18,70,-40,0,54,72,0,1,54,-7,-14,17,54,54,10,2,1,36,0,100,85,-48,17,36,38,82,29,17,18,38,-42,32,17,18,-71,52,1,18,1,-76,-71,-24,1,18,1,90,38,-90,44,17,18,38,-104,79,17,18,38,56,22,1,18,1,72,38,-26,10,1,18,1,72,38,70,23,17,18,121,96,1,18,14,42,48,-71,-78,1,18,1,54,38,24,66,1,18,33,-116,38,76,35,17,18,34,-16,39,9,18,8,-109,-56,-28,-7,-68,5,36,8,101,-3,-121,25,-112,0,36,-119,56,0,92,-71,-114,17,18,38,104,10,17,18,38,72,9,17,18,-71,106,17,18,38,26,25,17,18,38,-16,12,0,38,18,-54,44,4,-45,-123,38,80,16,1,18,14,114,39,38,28,11,17,18,38,86,10,0,37,9,-94,0,96,38,88,23,13,18,0,94,38,6,12,17,18,38,56,13,13,18,0,97,38,-44,19,0,40,5,126,4,-41,-13,121,-34,1,18,12,78,-74,8,116,38,-76,9,17,18,38,44,25,1,18,33,50,38,-124,21,1,18,14,-62,46,-103,2,1,18,1,72,38,-2,13,0,43,9,-76,0,120,38,108,27,13,18,0,119,38,36,9,13,18,0,120,38,-120,11,13,18,0,119,38,66,15,13,18,0,120,38,118,20,17,18,38,-78,14,17,18,38,-2,13,17,18,38,108,18,17,18,38,24,12,17,18,38,72,18,17,18,38,36,9,17,18,38,60,30,17,18,70,90,0,38,86,10,17,36,38,-116,10,17,18,38,-66,11,0,39,41,32,0,119,38,-86,34,17,18,38,120,15,17,18,38,24,21,17,18,38,72,27,1,18,14,40,17,-103,-20,1,18,14,54,9,38,66,24,17,18,38,108,9,17,18,38,-94,18,1,18,1,72,38,-22,9,1,18,1,72,38,-42,14,17,18,89,-66,17,18,38,-40,54,1,18,65,28,-39,120,1,18,1,72,-7,80,17,18,89,-48,17,18,38,56,31,17,18,38,46,29,17,18,38,-114,32,1,18,1,108,-71,34,1,18,-127,20,38,-6,32,1,18,14,2,49,0,104,-75,16,5,18,8,-74,8,119,38,-112,27,17,18,38,-106,30,17,18,70,122,1,-39,-64,17,36,38,114,30,1,18,33,68,-7,-68,1,18,1,108,0,118,66,126,0,38,-22,27,17,36,38,22,8,17,18,-71,-60,0,41,-31,-32,8,-114,-7,105,38,30,15,5,18,8,-109,-56,-29,-103,2,1,18,14,-110,13,38,120,15,1,18,14,100,11,38,124,14,1,18,12,78,-74,8,90,38,54,9,1,18,1,72,38,-70,21,5,18,8,-114,-7,105,38,-66,29,1,18,1,54,38,-4,27,1,18,1,36,0,-75,21,-40,1,18,1,36,38,-4,9,17,18,38,44,34,1,18,1,54,70,18,0,38,-92,13,1,36,1,72,38,2,22,1,18,1,54,38,-62,10,1,18,1,36,54,18,0,1,-58,38,126,9,17,36,34,-116,46,21,18,-103,-92,1,36,1,90,38,-66,11,17,18,38,40,26,5,18,8,-109,-56,-29,-103,-110,5,18,8,-114,-7,105,38,10,11,1,18,1,-112,38,50,28,1,18,1,54,38,-78,23,5,18,8,-114,-7,105,38,6,12,1,18,1,54,89,100,1,18,1,36,54,-4,0,1,36,89,64,1,36,1,18,89,-84,1,18,1,54,38,126,9,17,18,54,46,2,1,54,-7,44,17,36,121,42,1,18,1,36,38,118,11,1,18,1,90,54,46,2,1,36,38,96,21,1,36,14,-36,17,-39,66,1,18,1,54,38,-84,29,1,18,1,54,38,96,39,1,18,1,54,38,82,38,1,18,1,36,38,84,15,1,18,65,-66,38,36,9,5,18,8,-114,-7,105,38,38,13,17,18,54,82,2,1,90,38,-22,36,1,36,1,18,121,96,1,18,1,72,-7,-86,1,18,1,126,58,86,1,8,-109,-56,-29,38,-46,42,17,36,-71,88,1,18,1,36,38,-68,16,1,18,1,72,-103,-56,1,18,1,108,70,122,1,38,-90,8,1,36,1,54,54,-120,2,1,18,-103,38,13,36,0,89,38,-70,39,13,18,0,90,54,104,1,1,108,0,-94,66,-106,3,38,0,9,17,54,70,126,0,54,-52,3,-127,74,-71,106,17,54,38,-8,10,1,18,1,108,58,46,2,8,-109,-56,-29,38,-94,36,5,36,8,-109,-56,-29,38,0,18,5,18,66,60,3,1,18,58,90,0,8,-109,-55,1,38,-106,21,17,54,38,-78,14,1,18,33,32,54,10,2,1,18,38,106,14,0,44,-87,52,0,107,38,126,27,17,18,38,110,13,17,18,89,118,17,18,-7,-86,17,18,38,-60,41,13,18,0,106,38,46,20,13,18,0,107,38,-30,29,13,18,0,106,89,28,13,18,0,107,38,-72,8,17,18,38,0,9,17,18,70,-94,0,121,60,17,36,38,112,8,17,18,38,90,18,13,18,0,106,38,24,30,13,18,0,107,38,-24,41,13,18,0,106,-71,52,17,18,-103,-74,13,18,0,107,38,36,9,13,18,0,106,38,2,22,13,18,0,107,38,-18,8,17,18,38,108,9,13,18,0,106,-39,-82,17,18,89,46,17,18,89,-30,17,18,38,50,10,13,18,0,107,38,-112,9,17,18,38,-4,9,17,18,38,-94,9,13,18,0,106,38,86,19,17,18,70,-98,1,38,-4,9,17,36,38,100,20,17,18,-7,44,13,18,0,107,38,-26,10,17,18,38,-80,10,13,18,0,106,34,-102,11,4,25,100,22,-4,9,0,94,-107,-38,21,18,34,-54,26,5,18,14,-88,30,34,-110,13,5,18,14,64,20,34,2,13,5,18,14,-8,19,34,-84,20,5,18,1,36,34,-102,65,21,18,34,-24,14,21,18,54,90,0,1,72,34,-16,12,5,36,1,18,34,-108,35,5,18,1,90,34,70,14,5,18,1,36,34,-34,12,5,18,1,-76,34,-10,15,5,18,1,54,34,-20,13,21,18,34,56,49,21,18,34,-112,36,5,18,14,34,32,34,-44,10,5,18,1,72,34,-88,48,21,18,-11,116,21,18,34,-52,39,21,18,34,-90,35,5,18,1,-94,34,90,27,5,18,1,-58,34,10,29,5,18,1,108,34,-2,22,5,18,16,79,64,-45,-122,24,-79,88,5,18,1,36,34,44,16,21,18,34,112,26,21,18,34,-46,15,21,18,34,-66,20,21,18,34,82,11,5,18,1,-112,34,40,8,21,18,34,4,26,5,18,1,126,34,-18,44,5,18,14,-24,14,34,26,43,9,18,8,-114,-7,106,34,78,30,5,18,1,54,54,68,1,1,36,-75,88,21,36,34,26,16,21,18,34,64,65,21,18,34,66,15,5,18,1,72,58,-94,0,8,-3,1,-66,-107,110,21,36,34,-100,24,21,18,34,94,26,5,18,33,-98,70,-8,1,34,20,13,5,36,1,108,-11,-68,5,18,1,-40,70,-112,0,34,-14,25,5,36,1,54,34,-12,29,5,18,1,54,34,14,46,5,18,1,126,70,-62,1,70,-112,0,54,6,3,1,72,34,-86,70,5,72,1,18,54,100,2,1,18,34,88,23,5,36,1,-112,70,118,2,34,-20,22,9,36,8,-109,-56,-28,34,-60,23,9,18,8,-114,-7,106,34,-122,16,5,18,1,90,34,126,18,21,18,34,-106,30,5,18,1,54,34,-122,43,5,18,1,54,34,-112,72,21,18,70,54,0,34,-100,33,21,36,34,-76,9,5,18,1,90,34,16,32,5,18,1,90,34,-42,14,21,18,34,-4,18,21,18,34,-108,8,5,18,33,122,44,32,16,0,0,0,0,1,0,0,25,100,0,0,8,-114,-7,110,34,58,32,1,12,50,30,0,14,-78,17,17,-106,5,12,62,30,0,0,104,93,-108,0,104,54,-108,2,97,0,0,24,125,12,0,24,62,60,0,0,100,42,-84,8,0,100,70,-84,8,-107,86,8,-114,-7,110,66,86,4,0,110,42,106,14,0,110,70,106,14,30,-54,8,97,72,54,-54,8,-127,44,30,-100,9,5,12,62,-106,0,0,101,30,78,42,-63,54,54,78,42,14,24,39,30,-50,49,5,12,50,60,0,65,76,14,-26,70,77,-18,0,109,38,-26,70,69,-18,0,101,114,-30,14,8,-114,-7,110,14,118,77,13,60,0,110,38,118,77,5,60,4,-114,-7,34,100,35,5,12,50,120,0,65,28,-47,-82,5,12,50,30,0,65,-120,14,-46,60,5,90,8,101,-3,-122,38,-46,60,1,90,65,-30,113,-94,5,12,50,60,0,65,46,14,-52,66,1,60,5,12,62,30,0,0,110,30,-16,30,-127,-50,54,-16,30,1,-88,30,92,28,5,12,50,60,0,33,14,-15,-98,5,12,50,30,0,-95,-108,30,70,50,5,12,50,30,0,1,-58,34,-36,35,8,101,-3,-122,54,-36,35,1,-58,42,46,14,0,104,54,46,14,33,-92,114,-36,35,0,110,14,-104,73,1,-16,1,-76,38,104,76,45,44,0,103,42,114,21,0,103,54,114,21,1,-58,0,12,77,-18,5,12,54,-76,0,14,-74,16,17,30,1,12,50,30,0,1,-28,30,-76,15,5,12,50,30,0,97,120,42,-30,29,0,113,58,-30,29,8,101,-3,-121,34,18,12,1,12,50,60,0,1,-58,14,72,63,17,-46,38,-114,83,1,-46,33,14,34,-118,42,8,-114,-7,109,54,-118,42,1,60,0,26,17,-76,12,-114,-7,110,26,50,90,0,65,16,30,88,32,5,12,66,30,0,113,102,1,30,54,102,3,1,108,0,-59,25,90,4,109,-59,50,60,0,97,-106,14,110,55,1,-76,5,12,62,30,0,14,121,94,17,30,0,-14,54,122,28,1,48,30,120,15,5,12,50,60,0,33,122,30,-66,50,5,12,50,30,0,1,48,113,12,5,12,50,30,0,14,-118,30,34,58,17,8,-114,-7,108,54,58,17,1,-46,30,-122,16,5,12,62,60,0,110,104,1,8,101,-3,-122,30,-122,16,5,12,54,60,0,4,-109,-55,118,-46,30,0,110,42,66,54,0,110,54,66,54,65,58,42,44,16,0,113,58,44,16,8,-114,-7,110,30,80,55,5,12,50,120,0,33,2,14,-94,63,49,-122,38,-94,63,77,58,0,110,34,4,11,8,-114,-7,110,70,4,11,30,58,17,1,30,58,58,17,-63,-34,57,-2,58,-22,6,33,2,-79,-36,5,12,50,-106,0,65,-30,106,48,12,0,101]

compressedOffset = 0

compressedSize = 115

Snappy will crash in UnsafeMemory.copyLong().

Here's the call stack with values from a debug session, just before the access violation:

UnsafeMemory:

(comment: trying to read offset 2123344593 from a 107 byte array)

SnappyInternalUtils:

SnappyDecompressor:

SnappyDecompressor:

(note: trailer = -2123344593)

still live?

Is this project still being maintained?
It would be great if the framing format and osgi bundle changes could be incorporated.

when will 0.4 release?

I need a released version for maven dependency, so is there a eta or something that 0.4 will be released.

Please tag 0.4 release

snappy-0.4 is released, but it's not tagged in git, so it's not possible to download release from Github.

Please git tag snappy-0.4 e02f7c8 to fix this.

Compatibility with JDK 1.5

Is it possible to release the jar that is compiled for JDK 1.5 and not limited to 1.6?

Framed IO doesn't work with DataInputStream/DataOutputStream

Hi @dain

Sorry if I'm doing something stupid, but I can't see what it is.

I'm trying to write compressed longs to a file using java.io.DataOutputStream. The write seems to work, but the read fails without an exception. For example, in the test below, the snappy version produces no output when reading, but the plain buffered IO version does:

  @Test 
  public void testSnappy() throws Exception {

    System.out.println("With snappy:");

    String fileName = "foob.bar";
    try (FileOutputStream fos = new FileOutputStream(fileName);
         SnappyFramedOutputStream sos = new SnappyFramedOutputStream(fos);
         DataOutputStream dos = new DataOutputStream(sos)) {
      for(long i = 0; i < 3; i++) {
        dos.writeLong(i);
        System.out.println(i);
      }
      dos.flush();
    }

    try (FileInputStream fis = new FileInputStream(fileName);
         SnappyFramedInputStream sis = new SnappyFramedInputStream(fis, true);
         DataInputStream dis = new DataInputStream(sis)) {
      while(dis.available() > 0) {
        long cell = dis.readLong();
        System.out.println(cell);
      }
    }

    System.out.println("Now with bufferedIO and no snappy:");
    fileName = "foob.bar1";
    try (FileOutputStream fos = new FileOutputStream(fileName);
         BufferedOutputStream sos = new BufferedOutputStream(fos);
         DataOutputStream dos = new DataOutputStream(sos)) {
      for(long i = 0; i < 3; i++) {
        dos.writeLong(i);
        System.out.println(i);
      }
      dos.flush();
    }

    try (FileInputStream fis = new FileInputStream(fileName);
         BufferedInputStream sis = new BufferedInputStream(fis);
         DataInputStream dis = new DataInputStream(sis)) {
      while(dis.available() > 0) {
        long cell = dis.readLong();
        System.out.println(cell);
      }
    }
  }

In the Snappy version, it produces no output because the call to available() returns 0 as the values of both position and valid are 0 in AbstractSnappyInputStream.

Stream format without requiring streams

As far as I understand, there is no way to get the stream format without using streams. In Voldemort, we have the data in a byte[] and it's wasteful to use a stream for the compression step.

At the same time, it would be nice to add a checksum and potentially avoid compression for cases where it doesn't help (like the stream format does). It's not too much work to do it manually, but it would be great if it was available as an out of the box method.

Use byte array scale in UnsafeMemory

The methods that access byte arrays need to multiply the index by the arrayIndexScale() for byte arrays.

SnappyOutputStream.close() throws an exception if already closed

The close() method calls flush() before checking whether the stream is already closed. If the stream is closed, flush() fails with an exception. I suggest enclosing the entire method in the "if (!closed)" check as follows:

@Override
public void close()
        throws IOException
{
    if (!closed) {
        try {
            flush();
            out.close();
        }
        finally {
            closed = true;
            recycler.releaseOutputBuffer(outputBuffer);
            recycler.releaseEncodeBuffer(buffer);
        }
    }
}

JVM core dumps on invalid (non-Snappy) input to org.iq80.snappy.Snappy/uncompress

Hi there,

I'm seeing a relatively large number of JVM core dumps (OpenJDK6+7, OracleJDK7) when speculatively trying to decompress bytes that turn out to not actually be compressed.

I'd expect an exception in this case, not a core dump. Two questions:

Is this a bug, or are my expectations off?
Either way, any suggested workarounds for the moment? This implementation doesn't seem to have an equivalent of http://wiki.snappy-java.googlecode.com/hg/apidocs/org/xerial/snappy/Snappy.html#isValidCompressedBuffer(byte[]) as far as I can tell.

Example core-dump header (I can upload/email a full dump if it'd help):

#
# A fatal error has been detected by the Java Runtime Environment:
#
#  SIGSEGV (0xb) at pc=0x000000010396c1d2, pid=48055, tid=4352880640
#
# JRE version: 7.0_04-b21
# Java VM: Java HotSpot(TM) 64-Bit Server VM (23.0-b21 mixed mode bsd-amd64 compressed oops)
# Problematic frame:
# J  org.iq80.snappy.SnappyInternalUtils.copyLong([BI[BI)V

Thanks a lot for the great library and any assistance!

Peter

OSGi support

Could you provide OSGi support for your library a Manifest would have to look like the Code below. You can generate such Manifest either automatically via maven-bundle-plugin or you just attach a predefined Manifest with the maven-jar-plugin.

Manifest-Version: 1.0
Bundle-ManifestVersion: 2
Bundle-Name: Snappy
Bundle-SymbolicName: org.iq80.snappy
Bundle-Version: 0.4.0
Export-Package: org.iq80.snappy;version="0.4.0"
Bundle-RequiredExecutionEnvironment: JavaSE-1.6

org.xerial.snappy/snappy-java to be upgraded from 1.0.3 to 1.0.4.1

org.xerial.snappy / snappy-java has made a release of 1.0.4.1 , as of Oct 2011.

(http://code.google.com/p/snappy-java/downloads/list) .

Need to update the pom.xml to reflect the version change.