You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by mt...@apache.org on 2009/08/30 13:14:20 UTC
svn commit: r809313 [1/3] - in /commons/sandbox/runtime/trunk: ./
src/main/native/ src/main/native/srclib/bzip2/ src/main/native/test/
Author: mturk
Date: Sun Aug 30 11:14:19 2009
New Revision: 809313
URL: http://svn.apache.org/viewvc?rev=809313&view=rev
Log:
Add API prefixed bzlib
Added:
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/bzlib.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/bzlib.h (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/bzlib_private.h (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/compress.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/crctable.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/decompress.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/huffman.c (with props)
commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/randtable.c (with props)
Modified:
commons/sandbox/runtime/trunk/LICENSE.txt
commons/sandbox/runtime/trunk/src/main/native/Makefile.in
commons/sandbox/runtime/trunk/src/main/native/Makefile.msc.in
commons/sandbox/runtime/trunk/src/main/native/test/testsuite.c
Modified: commons/sandbox/runtime/trunk/LICENSE.txt
URL: http://svn.apache.org/viewvc/commons/sandbox/runtime/trunk/LICENSE.txt?rev=809313&r1=809312&r2=809313&view=diff
==============================================================================
--- commons/sandbox/runtime/trunk/LICENSE.txt (original)
+++ commons/sandbox/runtime/trunk/LICENSE.txt Sun Aug 30 11:14:19 2009
@@ -201,176 +201,213 @@
limitations under the License.
-APACHE COMMONS RUNTIME SUBCOMPONENTS:
+APACHE COMMONS RUNTIME SUBCOMPONENTS:
The Apache HTTP Server includes a number of subcomponents with
separate copyright notices and license terms. Your use of the source
code for the these subcomponents is subject to the terms and
-conditions of the following licenses.
+conditions of the following licenses.
For the MD5 Message-Digest library component:
- Copyright (C) 1995, Board of Trustees of the University of Illinois
+ Copyright (C) 1995, Board of Trustees of the University of Illinois
- *********************************************************************
+ *********************************************************************
- (C) Copyright 1993,1994 by Carnegie Mellon University
- All Rights Reserved.
+ (C) Copyright 1993,1994 by Carnegie Mellon University
+ All Rights Reserved.
- Permission to use, copy, modify, distribute, and sell this software
- and its documentation for any purpose is hereby granted without
- fee, provided that the above copyright notice appear in all copies
- and that both that copyright notice and this permission notice
- appear in supporting documentation, and that the name of Carnegie
- Mellon University not be used in advertising or publicity
- pertaining to distribution of the software without specific,
- written prior permission. Carnegie Mellon University makes no
- representations about the suitability of this software for any
- purpose. It is provided "as is" without express or implied
- warranty.
-
- CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
- THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
- AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
- FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
- AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
- OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
- SOFTWARE.
-
- *********************************************************************
-
- Copyright (c) 1991 Bell Communications Research, Inc. (Bellcore)
-
- Permission to use, copy, modify, and distribute this material
- for any purpose and without fee is hereby granted, provided
- that the above copyright notice and this permission notice
- appear in all copies, and that the name of Bellcore not be
- used in advertising or publicity pertaining to this
- material without the specific, prior written permission
- of an authorized representative of Bellcore. BELLCORE
- MAKES NO REPRESENTATIONS ABOUT THE ACCURACY OR SUITABILITY
- OF THIS MATERIAL FOR ANY PURPOSE. IT IS PROVIDED "AS IS",
- WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES.
-
- *********************************************************************
-
- Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
- rights reserved.
-
- License to copy and use this software is granted provided that it
- is identified as the "RSA Data Security, Inc. MD5 Message-Digest
- Algorithm" in all material mentioning or referencing this software
- or this function.
-
- License is also granted to make and use derivative works provided
- that such works are identified as "derived from the RSA Data
- Security, Inc. MD5 Message-Digest Algorithm" in all material
- mentioning or referencing the derived work.
-
- RSA Data Security, Inc. makes no representations concerning either
- the merchantability of this software or the suitability of this
- software for any particular purpose. It is provided "as is"
- without express or implied warranty of any kind.
-
- These notices must be retained in any copies of any part of this
- documentation and/or software.
-
- ----------------------------------------------------------------------------
- "THE BEER-WARE LICENSE" (Revision 42):
- <ph...@login.dknet.dk> wrote this file. As long as you retain this notice you
- can do whatever you want with this stuff. If we meet some day, and you think
- this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
- ----------------------------------------------------------------------------
+ Permission to use, copy, modify, distribute, and sell this software
+ and its documentation for any purpose is hereby granted without
+ fee, provided that the above copyright notice appear in all copies
+ and that both that copyright notice and this permission notice
+ appear in supporting documentation, and that the name of Carnegie
+ Mellon University not be used in advertising or publicity
+ pertaining to distribution of the software without specific,
+ written prior permission. Carnegie Mellon University makes no
+ representations about the suitability of this software for any
+ purpose. It is provided "as is" without express or implied
+ warranty.
+
+ CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
+ THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+ AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
+ FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
+ AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
+ OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
+ SOFTWARE.
+
+ *********************************************************************
+
+ Copyright (c) 1991 Bell Communications Research, Inc. (Bellcore)
+
+ Permission to use, copy, modify, and distribute this material
+ for any purpose and without fee is hereby granted, provided
+ that the above copyright notice and this permission notice
+ appear in all copies, and that the name of Bellcore not be
+ used in advertising or publicity pertaining to this
+ material without the specific, prior written permission
+ of an authorized representative of Bellcore. BELLCORE
+ MAKES NO REPRESENTATIONS ABOUT THE ACCURACY OR SUITABILITY
+ OF THIS MATERIAL FOR ANY PURPOSE. IT IS PROVIDED "AS IS",
+ WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES.
+
+ *********************************************************************
+
+ Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
+ rights reserved.
+
+ License to copy and use this software is granted provided that it
+ is identified as the "RSA Data Security, Inc. MD5 Message-Digest
+ Algorithm" in all material mentioning or referencing this software
+ or this function.
+
+ License is also granted to make and use derivative works provided
+ that such works are identified as "derived from the RSA Data
+ Security, Inc. MD5 Message-Digest Algorithm" in all material
+ mentioning or referencing the derived work.
+
+ RSA Data Security, Inc. makes no representations concerning either
+ the merchantability of this software or the suitability of this
+ software for any particular purpose. It is provided "as is"
+ without express or implied warranty of any kind.
+
+ These notices must be retained in any copies of any part of this
+ documentation and/or software.
+
+ ----------------------------------------------------------------------------
+ "THE BEER-WARE LICENSE" (Revision 42):
+ <ph...@login.dknet.dk> wrote this file. As long as you retain this notice you
+ can do whatever you want with this stuff. If we meet some day, and you think
+ this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
+ ----------------------------------------------------------------------------
+
+For the bzlib library component:
+
+ This program, "bzip2", the associated library "libbzip2", and all
+ documentation, are copyright (C) 1996-2007 Julian R Seward. All
+ rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+
+ 1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+ 2. The origin of this software must not be misrepresented; you must
+ not claim that you wrote the original software. If you use this
+ software in a product, an acknowledgment in the product
+ documentation would be appreciated but is not required.
+
+ 3. Altered source versions must be plainly marked as such, and must
+ not be misrepresented as being the original software.
+
+ 4. The name of the author may not be used to endorse or promote
+ products derived from this software without specific prior written
+ permission.
+
+ THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
+ OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+ GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
For the regex library component:
- Copyright 1992, 1993, 1994 Henry Spencer. All rights reserved.
- This software is not subject to any license of the American Telephone
- and Telegraph Company or of the Regents of the University of California.
-
- Permission is granted to anyone to use this software for any purpose on
- any computer system, and to alter it and redistribute it, subject
- to the following restrictions:
-
- 1. The author is not responsible for the consequences of use of this
- software, no matter how awful, even if they arise from flaws in it.
-
- 2. The origin of this software must not be misrepresented, either by
- explicit claim or by omission. Since few users ever read sources,
- credits must appear in the documentation.
-
- 3. Altered versions must be plainly marked as such, and must not be
- misrepresented as being the original software. Since few users
- ever read sources, credits must appear in the documentation.
+ Copyright 1992, 1993, 1994 Henry Spencer. All rights reserved.
+ This software is not subject to any license of the American Telephone
+ and Telegraph Company or of the Regents of the University of California.
+
+ Permission is granted to anyone to use this software for any purpose on
+ any computer system, and to alter it and redistribute it, subject
+ to the following restrictions:
+
+ 1. The author is not responsible for the consequences of use of this
+ software, no matter how awful, even if they arise from flaws in it.
+
+ 2. The origin of this software must not be misrepresented, either by
+ explicit claim or by omission. Since few users ever read sources,
+ credits must appear in the documentation.
+
+ 3. Altered versions must be plainly marked as such, and must not be
+ misrepresented as being the original software. Since few users
+ ever read sources, credits must appear in the documentation.
- 4. This notice may not be removed or altered.
+ 4. This notice may not be removed or altered.
For the zlib library component:
- Copyright 1995-2004 Jean-loup Gailly and Mark Adler
+ Copyright 1995-2004 Jean-loup Gailly and Mark Adler
- This software is provided 'as-is', without any express or implied
- warranty. In no event will the authors be held liable for any damages
- arising from the use of this software.
-
- Permission is granted to anyone to use this software for any purpose,
- including commercial applications, and to alter it and redistribute it
- freely, subject to the following restrictions:
-
- 1. The origin of this software must not be misrepresented; you must not
- claim that you wrote the original software. If you use this software
- in a product, an acknowledgment in the product documentation would be
- appreciated but is not required.
- 2. Altered source versions must be plainly marked as such, and must not be
- misrepresented as being the original software.
- 3. This notice may not be removed or altered from any source distribution.
+ This software is provided 'as-is', without any express or implied
+ warranty. In no event will the authors be held liable for any damages
+ arising from the use of this software.
+
+ Permission is granted to anyone to use this software for any purpose,
+ including commercial applications, and to alter it and redistribute it
+ freely, subject to the following restrictions:
+
+ 1. The origin of this software must not be misrepresented; you must not
+ claim that you wrote the original software. If you use this software
+ in a product, an acknowledgment in the product documentation would be
+ appreciated but is not required.
+ 2. Altered source versions must be plainly marked as such, and must not be
+ misrepresented as being the original software.
+ 3. This notice may not be removed or altered from any source distribution.
From src/ap/ap_snprintf.c:
- *
- * cvt - IEEE floating point formatting routines.
- * Derived from UNIX V7, Copyright(C) Caldera International Inc.
- *
-
- Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are
- met:
-
- Redistributions of source code and documentation must retain the above
- copyright notice, this list of conditions and the following disclaimer.
-
- Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- All advertising materials mentioning features or use of this software
- must display the following acknowledgement:
-
- This product includes software developed or owned by Caldera
- International, Inc.
-
- Neither the name of Caldera International, Inc. nor the names of other
- contributors may be used to endorse or promote products derived from
- this software without specific prior written permission.
-
- USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
- INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED
- WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
- NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
- INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
+ *
+ * cvt - IEEE floating point formatting routines.
+ * Derived from UNIX V7, Copyright(C) Caldera International Inc.
+ *
+
+ Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are
+ met:
+
+ Redistributions of source code and documentation must retain the above
+ copyright notice, this list of conditions and the following disclaimer.
+
+ Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ All advertising materials mentioning features or use of this software
+ must display the following acknowledgement:
+
+ This product includes software developed or owned by Caldera
+ International, Inc.
+
+ Neither the name of Caldera International, Inc. nor the names of other
+ contributors may be used to endorse or promote products derived from
+ this software without specific prior written permission.
+
+ USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
+ INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
+ NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
+ INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ POSSIBILITY OF SUCH DAMAGE.
Modified: commons/sandbox/runtime/trunk/src/main/native/Makefile.in
URL: http://svn.apache.org/viewvc/commons/sandbox/runtime/trunk/src/main/native/Makefile.in?rev=809313&r1=809312&r2=809313&view=diff
==============================================================================
--- commons/sandbox/runtime/trunk/src/main/native/Makefile.in (original)
+++ commons/sandbox/runtime/trunk/src/main/native/Makefile.in Sun Aug 30 11:14:19 2009
@@ -73,6 +73,7 @@
$(SRCDIR)/os/unix \
$(SRCDIR)/os/win32 \
$(SRCDIR)/modules/network/ssl \
+ $(SRCDIR)/srclib/bzip2 \
$(SRCDIR)/srclib/regex \
$(SRCDIR)/srclib/zlib \
$(SRCDIR)/test
@@ -208,6 +209,15 @@
$(SRCDIR)/port/strlcpy.$(OBJ) \
$(SRCDIR)/port/strsignal.$(OBJ)
+BZIP2_OBJS=\
+ $(SRCDIR)/srclib/bzip2/blocksort.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/bzlib.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/compress.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/crctable.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/decompress.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/huffman.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/randtable.$(OBJ)
+
REGEX_OBJS=\
$(SRCDIR)/srclib/regex/regcomp.$(OBJ) \
$(SRCDIR)/srclib/regex/regerror.$(OBJ) \
@@ -244,12 +254,12 @@
.cpp.$(OBJ):
$(CXX) $(CFLAGS) $(CPPFLAGS) $(CXXFLAGS) $(INCLUDES) -c -o $@ $<
-$(STATICLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@
- $(AR) $(ARFLAGS) $@ $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@
+$(STATICLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@
+ $(AR) $(ARFLAGS) $@ $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@
$(RANLIB) $@
-$(SHAREDLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@ $(STATICLIB)
- $(CC) $(SHFLAGS) $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@ $(LDFLAGS) -o $@
+$(SHAREDLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@ $(STATICLIB)
+ $(CC) $(SHFLAGS) $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@ $(LDFLAGS) -o $@
$(SSLMODLIB): $(SHAREDLIB) $(OPENSSL_OBJS)
$(CC) $(EXLFLAGS) $(SHFLAGS) $(OPENSSL_OBJS) $(LDFLAGS) $(SSLFLAGS) -L. -l$(NAME) -o $@
Modified: commons/sandbox/runtime/trunk/src/main/native/Makefile.msc.in
URL: http://svn.apache.org/viewvc/commons/sandbox/runtime/trunk/src/main/native/Makefile.msc.in?rev=809313&r1=809312&r2=809313&view=diff
==============================================================================
--- commons/sandbox/runtime/trunk/src/main/native/Makefile.msc.in (original)
+++ commons/sandbox/runtime/trunk/src/main/native/Makefile.msc.in Sun Aug 30 11:14:19 2009
@@ -129,6 +129,15 @@
$(SRCDIR)/port/strlcpy.$(OBJ) \
$(SRCDIR)/port/strsignal.$(OBJ)
+BZIP2_OBJS=\
+ $(SRCDIR)/srclib/bzip2/blocksort.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/bzlib.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/compress.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/crctable.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/decompress.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/huffman.$(OBJ) \
+ $(SRCDIR)/srclib/bzip2/randtable.$(OBJ)
+
REGEX_OBJS=\
$(SRCDIR)/srclib/regex/regcomp.$(OBJ) \
$(SRCDIR)/srclib/regex/regerror.$(OBJ) \
@@ -166,6 +175,9 @@
{$(SRCDIR)\os\win32}.c{$(SRCDIR)\os\win32}.$(OBJ):
$(CC) $(CFLAGS) $(CPPFLAGS) -DACR_DECLARE_EXPORT $(INCLUDES) -c -Fo$@ -Fd$(LIBNAME)-src $<
+{$(SRCDIR)\srclib\bzip2}.c{$(SRCDIR)\srclib\bzip2}.$(OBJ):
+ $(CC) $(CFLAGS) $(CPPFLAGS) -DACR_DECLARE_EXPORT $(INCLUDES) -c -Fo$@ -Fd$(LIBNAME)-src $<
+
{$(SRCDIR)\srclib\regex}.c{$(SRCDIR)\srclib\regex}.$(OBJ):
$(CC) $(CFLAGS) $(CPPFLAGS) -DACR_DECLARE_EXPORT $(INCLUDES) -c -Fo$@ -Fd$(LIBNAME)-src $<
@@ -181,10 +193,10 @@
{$(SRCDIR)\modules\network\ssl}.c{$(SRCDIR)\modules\network\ssl}.$(OBJ):
$(CC) $(CFLAGS) $(CPPFLAGS) $(INCLUDES) -c -Fo$@ -Fd$(SSLNAME)-src $<
-$(SHAREDLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@
+$(SHAREDLIB): $(PPORT_OBJS) $(COMMON_OBJS) $(@platform@_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@
$(RC) /l 0x409 /d "NDEBUG" /i "$(SRCDIR)\include" /fo $@.res $(SRCDIR)/os/win32/main.rc
$(LINK) $(SHFLAGS) $(LDFLAGS) /DLL /SUBSYSTEM:WINDOWS /pdb:$(LIBNAME).pdb /out:$@ @<<
- $(PPORT_OBJS) $(COMMON_OBJS) $(WINDOWS_OBJS) $(REGEX_OBJS) $(ZLIB_OBJS) @testobjs@ $@.res
+ $(PPORT_OBJS) $(COMMON_OBJS) $(WINDOWS_OBJS) $(REGEX_OBJS) $(BZIP2_OBJS) $(ZLIB_OBJS) @testobjs@ $@.res
<<
IF EXIST $@.manifest \
mt -nologo -manifest $@.manifest -outputresource:$@;2
@@ -217,6 +229,7 @@
-@del /Q $(SRCDIR)\os\win32\*.$(OBJ) 2>NUL
-@del /Q $(SRCDIR)\os\win32\*.res 2>NUL
-@del /Q $(SRCDIR)\modules\network\ssl\*.$(OBJ) 2>NUL
+ -@del /Q $(SRCDIR)\srclib\bzip2\*.$(OBJ) 2>NUL
-@del /Q $(SRCDIR)\srclib\regex\*.$(OBJ) 2>NUL
-@del /Q $(SRCDIR)\srclib\zlib\*.$(OBJ) 2>NUL
-@del /Q *.dll 2>NUL
Added: commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE
URL: http://svn.apache.org/viewvc/commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE?rev=809313&view=auto
==============================================================================
--- commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE (added)
+++ commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE Sun Aug 30 11:14:19 2009
@@ -0,0 +1,42 @@
+
+--------------------------------------------------------------------------
+
+This program, "bzip2", the associated library "libbzip2", and all
+documentation, are copyright (C) 1996-2007 Julian R Seward. All
+rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions
+are met:
+
+1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+2. The origin of this software must not be misrepresented; you must
+ not claim that you wrote the original software. If you use this
+ software in a product, an acknowledgment in the product
+ documentation would be appreciated but is not required.
+
+3. Altered source versions must be plainly marked as such, and must
+ not be misrepresented as being the original software.
+
+4. The name of the author may not be used to endorse or promote
+ products derived from this software without specific prior written
+ permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
+OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+Julian Seward, jseward@bzip.org
+bzip2/libbzip2 version 1.0.5 of 10 December 2007
+
+--------------------------------------------------------------------------
Propchange: commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/LICENSE
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c
URL: http://svn.apache.org/viewvc/commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c?rev=809313&view=auto
==============================================================================
--- commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c (added)
+++ commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c Sun Aug 30 11:14:19 2009
@@ -0,0 +1,1094 @@
+
+/*-------------------------------------------------------------*/
+/*--- Block sorting machinery ---*/
+/*--- blocksort.c ---*/
+/*-------------------------------------------------------------*/
+
+/* ------------------------------------------------------------------
+ This file is part of bzip2/libbzip2, a program and library for
+ lossless, block-sorting data compression.
+
+ bzip2/libbzip2 version 1.0.5 of 10 December 2007
+ Copyright (C) 1996-2007 Julian Seward <js...@bzip.org>
+
+ Please read the WARNING, DISCLAIMER and PATENTS sections in the
+ README file.
+
+ This program is released under the terms of the license contained
+ in the file LICENSE.
+ ------------------------------------------------------------------ */
+
+
+#include "bzlib_private.h"
+
+/*---------------------------------------------*/
+/*--- Fallback O(N log(N)^2) sorting ---*/
+/*--- algorithm, for repetitive blocks ---*/
+/*---------------------------------------------*/
+
+/*---------------------------------------------*/
+static
+__inline__
+void fallbackSimpleSort ( UInt32* fmap,
+ UInt32* eclass,
+ Int32 lo,
+ Int32 hi )
+{
+ Int32 i, j, tmp;
+ UInt32 ec_tmp;
+
+ if (lo == hi) return;
+
+ if (hi - lo > 3) {
+ for ( i = hi-4; i >= lo; i-- ) {
+ tmp = fmap[i];
+ ec_tmp = eclass[tmp];
+ for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
+ fmap[j-4] = fmap[j];
+ fmap[j-4] = tmp;
+ }
+ }
+
+ for ( i = hi-1; i >= lo; i-- ) {
+ tmp = fmap[i];
+ ec_tmp = eclass[tmp];
+ for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
+ fmap[j-1] = fmap[j];
+ fmap[j-1] = tmp;
+ }
+}
+
+
+/*---------------------------------------------*/
+#define fswap(zz1, zz2) \
+ { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
+
+#define fvswap(zzp1, zzp2, zzn) \
+{ \
+ Int32 yyp1 = (zzp1); \
+ Int32 yyp2 = (zzp2); \
+ Int32 yyn = (zzn); \
+ while (yyn > 0) { \
+ fswap(fmap[yyp1], fmap[yyp2]); \
+ yyp1++; yyp2++; yyn--; \
+ } \
+}
+
+
+#define fmin(a,b) ((a) < (b)) ? (a) : (b)
+
+#define fpush(lz,hz) { stackLo[sp] = lz; \
+ stackHi[sp] = hz; \
+ sp++; }
+
+#define fpop(lz,hz) { sp--; \
+ lz = stackLo[sp]; \
+ hz = stackHi[sp]; }
+
+#define FALLBACK_QSORT_SMALL_THRESH 10
+#define FALLBACK_QSORT_STACK_SIZE 100
+
+
+static
+void fallbackQSort3 ( UInt32* fmap,
+ UInt32* eclass,
+ Int32 loSt,
+ Int32 hiSt )
+{
+ Int32 unLo, unHi, ltLo, gtHi, n, m;
+ Int32 sp, lo, hi;
+ UInt32 med, r, r3;
+ Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
+ Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
+
+ r = 0;
+
+ sp = 0;
+ fpush ( loSt, hiSt );
+
+ while (sp > 0) {
+
+ AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );
+
+ fpop ( lo, hi );
+ if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
+ fallbackSimpleSort ( fmap, eclass, lo, hi );
+ continue;
+ }
+
+ /* Random partitioning. Median of 3 sometimes fails to
+ avoid bad cases. Median of 9 seems to help but
+ looks rather expensive. This too seems to work but
+ is cheaper. Guidance for the magic constants
+ 7621 and 32768 is taken from Sedgewick's algorithms
+ book, chapter 35.
+ */
+ r = ((r * 7621) + 1) % 32768;
+ r3 = r % 3;
+ if (r3 == 0) med = eclass[fmap[lo]]; else
+ if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
+ med = eclass[fmap[hi]];
+
+ unLo = ltLo = lo;
+ unHi = gtHi = hi;
+
+ while (1) {
+ while (1) {
+ if (unLo > unHi) break;
+ n = (Int32)eclass[fmap[unLo]] - (Int32)med;
+ if (n == 0) {
+ fswap(fmap[unLo], fmap[ltLo]);
+ ltLo++; unLo++;
+ continue;
+ };
+ if (n > 0) break;
+ unLo++;
+ }
+ while (1) {
+ if (unLo > unHi) break;
+ n = (Int32)eclass[fmap[unHi]] - (Int32)med;
+ if (n == 0) {
+ fswap(fmap[unHi], fmap[gtHi]);
+ gtHi--; unHi--;
+ continue;
+ };
+ if (n < 0) break;
+ unHi--;
+ }
+ if (unLo > unHi) break;
+ fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
+ }
+
+ AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
+
+ if (gtHi < ltLo) continue;
+
+ n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
+ m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
+
+ n = lo + unLo - ltLo - 1;
+ m = hi - (gtHi - unHi) + 1;
+
+ if (n - lo > hi - m) {
+ fpush ( lo, n );
+ fpush ( m, hi );
+ } else {
+ fpush ( m, hi );
+ fpush ( lo, n );
+ }
+ }
+}
+
+#undef fmin
+#undef fpush
+#undef fpop
+#undef fswap
+#undef fvswap
+#undef FALLBACK_QSORT_SMALL_THRESH
+#undef FALLBACK_QSORT_STACK_SIZE
+
+
+/*---------------------------------------------*/
+/* Pre:
+ nblock > 0
+ eclass exists for [0 .. nblock-1]
+ ((UChar*)eclass) [0 .. nblock-1] holds block
+ ptr exists for [0 .. nblock-1]
+
+ Post:
+ ((UChar*)eclass) [0 .. nblock-1] holds block
+ All other areas of eclass destroyed
+ fmap [0 .. nblock-1] holds sorted order
+ bhtab [ 0 .. 2+(nblock/32) ] destroyed
+*/
+
+#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
+#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
+#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
+#define WORD_BH(zz) bhtab[(zz) >> 5]
+#define UNALIGNED_BH(zz) ((zz) & 0x01f)
+
+static
+void fallbackSort ( UInt32* fmap,
+ UInt32* eclass,
+ UInt32* bhtab,
+ Int32 nblock,
+ Int32 verb )
+{
+ Int32 ftab[257];
+ Int32 ftabCopy[256];
+ Int32 H, i, j, k, l, r, cc, cc1;
+ Int32 nNotDone;
+ Int32 nBhtab;
+ UChar* eclass8 = (UChar*)eclass;
+
+ /*--
+ Initial 1-char radix sort to generate
+ initial fmap and initial BH bits.
+ --*/
+ if (verb >= 4)
+ VPrintf0 ( " bucket sorting ...\n" );
+ for (i = 0; i < 257; i++) ftab[i] = 0;
+ for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
+ for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
+ for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
+
+ for (i = 0; i < nblock; i++) {
+ j = eclass8[i];
+ k = ftab[j] - 1;
+ ftab[j] = k;
+ fmap[k] = i;
+ }
+
+ nBhtab = 2 + (nblock / 32);
+ for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
+ for (i = 0; i < 256; i++) SET_BH(ftab[i]);
+
+ /*--
+ Inductively refine the buckets. Kind-of an
+ "exponential radix sort" (!), inspired by the
+ Manber-Myers suffix array construction algorithm.
+ --*/
+
+ /*-- set sentinel bits for block-end detection --*/
+ for (i = 0; i < 32; i++) {
+ SET_BH(nblock + 2*i);
+ CLEAR_BH(nblock + 2*i + 1);
+ }
+
+ /*-- the log(N) loop --*/
+ H = 1;
+ while (1) {
+
+ if (verb >= 4)
+ VPrintf1 ( " depth %6d has ", H );
+
+ j = 0;
+ for (i = 0; i < nblock; i++) {
+ if (ISSET_BH(i)) j = i;
+ k = fmap[i] - H; if (k < 0) k += nblock;
+ eclass[k] = j;
+ }
+
+ nNotDone = 0;
+ r = -1;
+ while (1) {
+
+ /*-- find the next non-singleton bucket --*/
+ k = r + 1;
+ while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
+ if (ISSET_BH(k)) {
+ while (WORD_BH(k) == 0xffffffff) k += 32;
+ while (ISSET_BH(k)) k++;
+ }
+ l = k - 1;
+ if (l >= nblock) break;
+ while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
+ if (!ISSET_BH(k)) {
+ while (WORD_BH(k) == 0x00000000) k += 32;
+ while (!ISSET_BH(k)) k++;
+ }
+ r = k - 1;
+ if (r >= nblock) break;
+
+ /*-- now [l, r] bracket current bucket --*/
+ if (r > l) {
+ nNotDone += (r - l + 1);
+ fallbackQSort3 ( fmap, eclass, l, r );
+
+ /*-- scan bucket and generate header bits-- */
+ cc = -1;
+ for (i = l; i <= r; i++) {
+ cc1 = eclass[fmap[i]];
+ if (cc != cc1) { SET_BH(i); cc = cc1; };
+ }
+ }
+ }
+
+ if (verb >= 4)
+ VPrintf1 ( "%6d unresolved strings\n", nNotDone );
+
+ H *= 2;
+ if (H > nblock || nNotDone == 0) break;
+ }
+
+ /*--
+ Reconstruct the original block in
+ eclass8 [0 .. nblock-1], since the
+ previous phase destroyed it.
+ --*/
+ if (verb >= 4)
+ VPrintf0 ( " reconstructing block ...\n" );
+ j = 0;
+ for (i = 0; i < nblock; i++) {
+ while (ftabCopy[j] == 0) j++;
+ ftabCopy[j]--;
+ eclass8[fmap[i]] = (UChar)j;
+ }
+ AssertH ( j < 256, 1005 );
+}
+
+#undef SET_BH
+#undef CLEAR_BH
+#undef ISSET_BH
+#undef WORD_BH
+#undef UNALIGNED_BH
+
+
+/*---------------------------------------------*/
+/*--- The main, O(N^2 log(N)) sorting ---*/
+/*--- algorithm. Faster for "normal" ---*/
+/*--- non-repetitive blocks. ---*/
+/*---------------------------------------------*/
+
+/*---------------------------------------------*/
+static
+__inline__
+Bool mainGtU ( UInt32 i1,
+ UInt32 i2,
+ UChar* block,
+ UInt16* quadrant,
+ UInt32 nblock,
+ Int32* budget )
+{
+ Int32 k;
+ UChar c1, c2;
+ UInt16 s1, s2;
+
+ AssertD ( i1 != i2, "mainGtU" );
+ /* 1 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 2 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 3 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 4 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 5 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 6 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 7 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 8 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 9 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 10 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 11 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+ /* 12 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ i1++; i2++;
+
+ k = nblock + 8;
+
+ do {
+ /* 1 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 2 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 3 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 4 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 5 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 6 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 7 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+ /* 8 */
+ c1 = block[i1]; c2 = block[i2];
+ if (c1 != c2) return (c1 > c2);
+ s1 = quadrant[i1]; s2 = quadrant[i2];
+ if (s1 != s2) return (s1 > s2);
+ i1++; i2++;
+
+ if (i1 >= nblock) i1 -= nblock;
+ if (i2 >= nblock) i2 -= nblock;
+
+ k -= 8;
+ (*budget)--;
+ }
+ while (k >= 0);
+
+ return False;
+}
+
+
+/*---------------------------------------------*/
+/*--
+ Knuth's increments seem to work better
+ than Incerpi-Sedgewick here. Possibly
+ because the number of elems to sort is
+ usually small, typically <= 20.
+--*/
+static
+Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
+ 9841, 29524, 88573, 265720,
+ 797161, 2391484 };
+
+static
+void mainSimpleSort ( UInt32* ptr,
+ UChar* block,
+ UInt16* quadrant,
+ Int32 nblock,
+ Int32 lo,
+ Int32 hi,
+ Int32 d,
+ Int32* budget )
+{
+ Int32 i, j, h, bigN, hp;
+ UInt32 v;
+
+ bigN = hi - lo + 1;
+ if (bigN < 2) return;
+
+ hp = 0;
+ while (incs[hp] < bigN) hp++;
+ hp--;
+
+ for (; hp >= 0; hp--) {
+ h = incs[hp];
+
+ i = lo + h;
+ while (True) {
+
+ /*-- copy 1 --*/
+ if (i > hi) break;
+ v = ptr[i];
+ j = i;
+ while ( mainGtU (
+ ptr[j-h]+d, v+d, block, quadrant, nblock, budget
+ ) ) {
+ ptr[j] = ptr[j-h];
+ j = j - h;
+ if (j <= (lo + h - 1)) break;
+ }
+ ptr[j] = v;
+ i++;
+
+ /*-- copy 2 --*/
+ if (i > hi) break;
+ v = ptr[i];
+ j = i;
+ while ( mainGtU (
+ ptr[j-h]+d, v+d, block, quadrant, nblock, budget
+ ) ) {
+ ptr[j] = ptr[j-h];
+ j = j - h;
+ if (j <= (lo + h - 1)) break;
+ }
+ ptr[j] = v;
+ i++;
+
+ /*-- copy 3 --*/
+ if (i > hi) break;
+ v = ptr[i];
+ j = i;
+ while ( mainGtU (
+ ptr[j-h]+d, v+d, block, quadrant, nblock, budget
+ ) ) {
+ ptr[j] = ptr[j-h];
+ j = j - h;
+ if (j <= (lo + h - 1)) break;
+ }
+ ptr[j] = v;
+ i++;
+
+ if (*budget < 0) return;
+ }
+ }
+}
+
+
+/*---------------------------------------------*/
+/*--
+ The following is an implementation of
+ an elegant 3-way quicksort for strings,
+ described in a paper "Fast Algorithms for
+ Sorting and Searching Strings", by Robert
+ Sedgewick and Jon L. Bentley.
+--*/
+
+#define mswap(zz1, zz2) \
+ { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
+
+#define mvswap(zzp1, zzp2, zzn) \
+{ \
+ Int32 yyp1 = (zzp1); \
+ Int32 yyp2 = (zzp2); \
+ Int32 yyn = (zzn); \
+ while (yyn > 0) { \
+ mswap(ptr[yyp1], ptr[yyp2]); \
+ yyp1++; yyp2++; yyn--; \
+ } \
+}
+
+static
+__inline__
+UChar mmed3 ( UChar a, UChar b, UChar c )
+{
+ UChar t;
+ if (a > b) { t = a; a = b; b = t; };
+ if (b > c) {
+ b = c;
+ if (a > b) b = a;
+ }
+ return b;
+}
+
+#define mmin(a,b) ((a) < (b)) ? (a) : (b)
+
+#define mpush(lz,hz,dz) { stackLo[sp] = lz; \
+ stackHi[sp] = hz; \
+ stackD [sp] = dz; \
+ sp++; }
+
+#define mpop(lz,hz,dz) { sp--; \
+ lz = stackLo[sp]; \
+ hz = stackHi[sp]; \
+ dz = stackD [sp]; }
+
+
+#define mnextsize(az) (nextHi[az]-nextLo[az])
+
+#define mnextswap(az,bz) \
+ { Int32 tz; \
+ tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
+ tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
+ tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
+
+
+#define MAIN_QSORT_SMALL_THRESH 20
+#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
+#define MAIN_QSORT_STACK_SIZE 100
+
+static
+void mainQSort3 ( UInt32* ptr,
+ UChar* block,
+ UInt16* quadrant,
+ Int32 nblock,
+ Int32 loSt,
+ Int32 hiSt,
+ Int32 dSt,
+ Int32* budget )
+{
+ Int32 unLo, unHi, ltLo, gtHi, n, m, med;
+ Int32 sp, lo, hi, d;
+
+ Int32 stackLo[MAIN_QSORT_STACK_SIZE];
+ Int32 stackHi[MAIN_QSORT_STACK_SIZE];
+ Int32 stackD [MAIN_QSORT_STACK_SIZE];
+
+ Int32 nextLo[3];
+ Int32 nextHi[3];
+ Int32 nextD [3];
+
+ sp = 0;
+ mpush ( loSt, hiSt, dSt );
+
+ while (sp > 0) {
+
+ AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );
+
+ mpop ( lo, hi, d );
+ if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
+ d > MAIN_QSORT_DEPTH_THRESH) {
+ mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
+ if (*budget < 0) return;
+ continue;
+ }
+
+ med = (Int32)
+ mmed3 ( block[ptr[ lo ]+d],
+ block[ptr[ hi ]+d],
+ block[ptr[ (lo+hi)>>1 ]+d] );
+
+ unLo = ltLo = lo;
+ unHi = gtHi = hi;
+
+ while (True) {
+ while (True) {
+ if (unLo > unHi) break;
+ n = ((Int32)block[ptr[unLo]+d]) - med;
+ if (n == 0) {
+ mswap(ptr[unLo], ptr[ltLo]);
+ ltLo++; unLo++; continue;
+ };
+ if (n > 0) break;
+ unLo++;
+ }
+ while (True) {
+ if (unLo > unHi) break;
+ n = ((Int32)block[ptr[unHi]+d]) - med;
+ if (n == 0) {
+ mswap(ptr[unHi], ptr[gtHi]);
+ gtHi--; unHi--; continue;
+ };
+ if (n < 0) break;
+ unHi--;
+ }
+ if (unLo > unHi) break;
+ mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
+ }
+
+ AssertD ( unHi == unLo-1, "mainQSort3(2)" );
+
+ if (gtHi < ltLo) {
+ mpush(lo, hi, d+1 );
+ continue;
+ }
+
+ n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
+ m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
+
+ n = lo + unLo - ltLo - 1;
+ m = hi - (gtHi - unHi) + 1;
+
+ nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
+ nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
+ nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
+
+ if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
+ if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
+ if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
+
+ AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
+ AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
+
+ mpush (nextLo[0], nextHi[0], nextD[0]);
+ mpush (nextLo[1], nextHi[1], nextD[1]);
+ mpush (nextLo[2], nextHi[2], nextD[2]);
+ }
+}
+
+#undef mswap
+#undef mvswap
+#undef mpush
+#undef mpop
+#undef mmin
+#undef mnextsize
+#undef mnextswap
+#undef MAIN_QSORT_SMALL_THRESH
+#undef MAIN_QSORT_DEPTH_THRESH
+#undef MAIN_QSORT_STACK_SIZE
+
+
+/*---------------------------------------------*/
+/* Pre:
+ nblock > N_OVERSHOOT
+ block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
+ ((UChar*)block32) [0 .. nblock-1] holds block
+ ptr exists for [0 .. nblock-1]
+
+ Post:
+ ((UChar*)block32) [0 .. nblock-1] holds block
+ All other areas of block32 destroyed
+ ftab [0 .. 65536 ] destroyed
+ ptr [0 .. nblock-1] holds sorted order
+ if (*budget < 0), sorting was abandoned
+*/
+
+#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
+#define SETMASK (1 << 21)
+#define CLEARMASK (~(SETMASK))
+
+static
+void mainSort ( UInt32* ptr,
+ UChar* block,
+ UInt16* quadrant,
+ UInt32* ftab,
+ Int32 nblock,
+ Int32 verb,
+ Int32* budget )
+{
+ Int32 i, j, k, ss, sb;
+ Int32 runningOrder[256];
+ Bool bigDone[256];
+ Int32 copyStart[256];
+ Int32 copyEnd [256];
+ UChar c1;
+ Int32 numQSorted;
+ UInt16 s;
+ if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
+
+ /*-- set up the 2-byte frequency table --*/
+ for (i = 65536; i >= 0; i--) ftab[i] = 0;
+
+ j = block[0] << 8;
+ i = nblock-1;
+ for (; i >= 3; i -= 4) {
+ quadrant[i] = 0;
+ j = (j >> 8) | ( ((UInt16)block[i]) << 8);
+ ftab[j]++;
+ quadrant[i-1] = 0;
+ j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
+ ftab[j]++;
+ quadrant[i-2] = 0;
+ j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
+ ftab[j]++;
+ quadrant[i-3] = 0;
+ j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
+ ftab[j]++;
+ }
+ for (; i >= 0; i--) {
+ quadrant[i] = 0;
+ j = (j >> 8) | ( ((UInt16)block[i]) << 8);
+ ftab[j]++;
+ }
+
+ /*-- (emphasises close relationship of block & quadrant) --*/
+ for (i = 0; i < BZ_N_OVERSHOOT; i++) {
+ block [nblock+i] = block[i];
+ quadrant[nblock+i] = 0;
+ }
+
+ if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
+
+ /*-- Complete the initial radix sort --*/
+ for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
+
+ s = block[0] << 8;
+ i = nblock-1;
+ for (; i >= 3; i -= 4) {
+ s = (s >> 8) | (block[i] << 8);
+ j = ftab[s] -1;
+ ftab[s] = j;
+ ptr[j] = i;
+ s = (s >> 8) | (block[i-1] << 8);
+ j = ftab[s] -1;
+ ftab[s] = j;
+ ptr[j] = i-1;
+ s = (s >> 8) | (block[i-2] << 8);
+ j = ftab[s] -1;
+ ftab[s] = j;
+ ptr[j] = i-2;
+ s = (s >> 8) | (block[i-3] << 8);
+ j = ftab[s] -1;
+ ftab[s] = j;
+ ptr[j] = i-3;
+ }
+ for (; i >= 0; i--) {
+ s = (s >> 8) | (block[i] << 8);
+ j = ftab[s] -1;
+ ftab[s] = j;
+ ptr[j] = i;
+ }
+
+ /*--
+ Now ftab contains the first loc of every small bucket.
+ Calculate the running order, from smallest to largest
+ big bucket.
+ --*/
+ for (i = 0; i <= 255; i++) {
+ bigDone [i] = False;
+ runningOrder[i] = i;
+ }
+
+ {
+ Int32 vv;
+ Int32 h = 1;
+ do h = 3 * h + 1; while (h <= 256);
+ do {
+ h = h / 3;
+ for (i = h; i <= 255; i++) {
+ vv = runningOrder[i];
+ j = i;
+ while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
+ runningOrder[j] = runningOrder[j-h];
+ j = j - h;
+ if (j <= (h - 1)) goto zero;
+ }
+ zero:
+ runningOrder[j] = vv;
+ }
+ } while (h != 1);
+ }
+
+ /*--
+ The main sorting loop.
+ --*/
+
+ numQSorted = 0;
+
+ for (i = 0; i <= 255; i++) {
+
+ /*--
+ Process big buckets, starting with the least full.
+ Basically this is a 3-step process in which we call
+ mainQSort3 to sort the small buckets [ss, j], but
+ also make a big effort to avoid the calls if we can.
+ --*/
+ ss = runningOrder[i];
+
+ /*--
+ Step 1:
+ Complete the big bucket [ss] by quicksorting
+ any unsorted small buckets [ss, j], for j != ss.
+ Hopefully previous pointer-scanning phases have already
+ completed many of the small buckets [ss, j], so
+ we don't have to sort them at all.
+ --*/
+ for (j = 0; j <= 255; j++) {
+ if (j != ss) {
+ sb = (ss << 8) + j;
+ if ( ! (ftab[sb] & SETMASK) ) {
+ Int32 lo = ftab[sb] & CLEARMASK;
+ Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
+ if (hi > lo) {
+ if (verb >= 4)
+ VPrintf4 ( " qsort [0x%x, 0x%x] "
+ "done %d this %d\n",
+ ss, j, numQSorted, hi - lo + 1 );
+ mainQSort3 (
+ ptr, block, quadrant, nblock,
+ lo, hi, BZ_N_RADIX, budget
+ );
+ numQSorted += (hi - lo + 1);
+ if (*budget < 0) return;
+ }
+ }
+ ftab[sb] |= SETMASK;
+ }
+ }
+
+ AssertH ( !bigDone[ss], 1006 );
+
+ /*--
+ Step 2:
+ Now scan this big bucket [ss] so as to synthesise the
+ sorted order for small buckets [t, ss] for all t,
+ including, magically, the bucket [ss,ss] too.
+ This will avoid doing Real Work in subsequent Step 1's.
+ --*/
+ {
+ for (j = 0; j <= 255; j++) {
+ copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
+ copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
+ }
+ for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
+ k = ptr[j]-1; if (k < 0) k += nblock;
+ c1 = block[k];
+ if (!bigDone[c1])
+ ptr[ copyStart[c1]++ ] = k;
+ }
+ for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
+ k = ptr[j]-1; if (k < 0) k += nblock;
+ c1 = block[k];
+ if (!bigDone[c1])
+ ptr[ copyEnd[c1]-- ] = k;
+ }
+ }
+
+ AssertH ( (copyStart[ss]-1 == copyEnd[ss])
+ ||
+ /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
+ Necessity for this case is demonstrated by compressing
+ a sequence of approximately 48.5 million of character
+ 251; 1.0.0/1.0.1 will then die here. */
+ (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
+ 1007 )
+
+ for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
+
+ /*--
+ Step 3:
+ The [ss] big bucket is now done. Record this fact,
+ and update the quadrant descriptors. Remember to
+ update quadrants in the overshoot area too, if
+ necessary. The "if (i < 255)" test merely skips
+ this updating for the last bucket processed, since
+ updating for the last bucket is pointless.
+
+ The quadrant array provides a way to incrementally
+ cache sort orderings, as they appear, so as to
+ make subsequent comparisons in fullGtU() complete
+ faster. For repetitive blocks this makes a big
+ difference (but not big enough to be able to avoid
+ the fallback sorting mechanism, exponential radix sort).
+
+ The precise meaning is: at all times:
+
+ for 0 <= i < nblock and 0 <= j <= nblock
+
+ if block[i] != block[j],
+
+ then the relative values of quadrant[i] and
+ quadrant[j] are meaningless.
+
+ else {
+ if quadrant[i] < quadrant[j]
+ then the string starting at i lexicographically
+ precedes the string starting at j
+
+ else if quadrant[i] > quadrant[j]
+ then the string starting at j lexicographically
+ precedes the string starting at i
+
+ else
+ the relative ordering of the strings starting
+ at i and j has not yet been determined.
+ }
+ --*/
+ bigDone[ss] = True;
+
+ if (i < 255) {
+ Int32 bbStart = ftab[ss << 8] & CLEARMASK;
+ Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
+ Int32 shifts = 0;
+
+ while ((bbSize >> shifts) > 65534) shifts++;
+
+ for (j = bbSize-1; j >= 0; j--) {
+ Int32 a2update = ptr[bbStart + j];
+ UInt16 qVal = (UInt16)(j >> shifts);
+ quadrant[a2update] = qVal;
+ if (a2update < BZ_N_OVERSHOOT)
+ quadrant[a2update + nblock] = qVal;
+ }
+ AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
+ }
+
+ }
+
+ if (verb >= 4)
+ VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
+ nblock, numQSorted, nblock - numQSorted );
+}
+
+#undef BIGFREQ
+#undef SETMASK
+#undef CLEARMASK
+
+
+/*---------------------------------------------*/
+/* Pre:
+ nblock > 0
+ arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
+ ((UChar*)arr2) [0 .. nblock-1] holds block
+ arr1 exists for [0 .. nblock-1]
+
+ Post:
+ ((UChar*)arr2) [0 .. nblock-1] holds block
+ All other areas of block destroyed
+ ftab [ 0 .. 65536 ] destroyed
+ arr1 [0 .. nblock-1] holds sorted order
+*/
+void BZ2_blockSort ( EState* s )
+{
+ UInt32* ptr = s->ptr;
+ UChar* block = s->block;
+ UInt32* ftab = s->ftab;
+ Int32 nblock = s->nblock;
+ Int32 verb = s->verbosity;
+ Int32 wfact = s->workFactor;
+ UInt16* quadrant;
+ Int32 budget;
+ Int32 budgetInit;
+ Int32 i;
+
+ if (nblock < 10000) {
+ fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
+ } else {
+ /* Calculate the location for quadrant, remembering to get
+ the alignment right. Assumes that &(block[0]) is at least
+ 2-byte aligned -- this should be ok since block is really
+ the first section of arr2.
+ */
+ i = nblock+BZ_N_OVERSHOOT;
+ if (i & 1) i++;
+ quadrant = (UInt16*)(&(block[i]));
+
+ /* (wfact-1) / 3 puts the default-factor-30
+ transition point at very roughly the same place as
+ with v0.1 and v0.9.0.
+ Not that it particularly matters any more, since the
+ resulting compressed stream is now the same regardless
+ of whether or not we use the main sort or fallback sort.
+ */
+ if (wfact < 1 ) wfact = 1;
+ if (wfact > 100) wfact = 100;
+ budgetInit = nblock * ((wfact-1) / 3);
+ budget = budgetInit;
+
+ mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
+ if (verb >= 3)
+ VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
+ budgetInit - budget,
+ nblock,
+ (float)(budgetInit - budget) /
+ (float)(nblock==0 ? 1 : nblock) );
+ if (budget < 0) {
+ if (verb >= 2)
+ VPrintf0 ( " too repetitive; using fallback"
+ " sorting algorithm\n" );
+ fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
+ }
+ }
+
+ s->origPtr = -1;
+ for (i = 0; i < s->nblock; i++)
+ if (ptr[i] == 0)
+ { s->origPtr = i; break; };
+
+ AssertH( s->origPtr != -1, 1003 );
+}
+
+
+/*-------------------------------------------------------------*/
+/*--- end blocksort.c ---*/
+/*-------------------------------------------------------------*/
Propchange: commons/sandbox/runtime/trunk/src/main/native/srclib/bzip2/blocksort.c
------------------------------------------------------------------------------
svn:eol-style = native