15 files changed, 4000 insertions, 583 deletions
diff --git a/package/cups/Makefile b/package/cups/Makefile
index 4d83cf472..f67813494 100644
--- a/package/cups/Makefile
+++ b/package/cups/Makefile
@@ -15,6 +15,7 @@ PKG_URL:=		http://www.cups.org/
 PKG_SITES:=		http://www.cups.org/software/${PKG_VERSION}/
 PKG_NEED_CXX:=		1
 PKG_OPTS:=		dev
+PKG_NOPARALLEL:=	1
 
 DISTFILES:=		${PKG_NAME}-${PKG_VERSION}-source.tar.bz2
 
@@ -32,6 +33,7 @@ HOST_STYLE:=		auto
 HOST_CONFIGURE_ARGS+=	--disable-tcp-wrappers \
 			--disable-webif \
 			--disable-gssapi \
+			--disable-avahi \
 			--disable-pam \
 			--disable-dbus \
 			--without-java \
@@ -46,10 +48,12 @@ HOST_CONFIGURE_ARGS+=	--disable-tcp-wrappers \
 			--with-components=core \
 			--with-rcdir=$(STAGING_HOST_DIR)/etc
 CONFIGURE_ENV+=		ac_cv_func_sigset=no \
-			OPTIM='-fPIC'
+			OPTIM='-fPIC -std=c89'
 
 CONFIGURE_ARGS+=	--with-cups-user=cups \
 			--with-cups-group=cups \
+			--disable-static \
+			--disable-avahi \
 			--disable-webif \
 			--disable-tcp-wrappers \
 			--disable-gssapi \
@@ -68,11 +72,6 @@ CONFIGURE_ARGS+=	--with-cups-user=cups \
 			--with-rcdir=$(STAGING_TARGET_DIR)/etc
 
 FAKE_FLAGS+=		DSTROOT="${WRKINST}" STRIP="/bin/true"
-ifeq ($(ADK_TOOLCHAIN_GCC_USE_SSP),y)
-XAKE_FLAGS+=		OPTIM='-fPIC -fstack-protector'
-else
-XAKE_FLAGS+=		OPTIM='-fPIC'
-endif
 
 cups-install:
 	${INSTALL_DIR} ${IDIR_CUPS}/usr/lib
diff --git a/package/cups/patches/patch-Makedefs_in b/package/cups/patches/patch-Makedefs_in
new file mode 100644
index 000000000..1a8f91894
--- /dev/null
+++ b/package/cups/patches/patch-Makedefs_in
@@ -0,0 +1,10 @@
+--- cups-1.7.1.orig/Makedefs.in	2013-07-17 17:21:18.000000000 +0200
++++ cups-1.7.1/Makedefs.in	2014-01-31 08:40:55.000000000 +0100
+@@ -238,7 +238,6 @@ DBUSDIR		=	@DBUSDIR@
+ # Rules...
+ #
+ 
+-.SILENT:
+ .SUFFIXES:	.1 .1.gz .1m .1m.gz .3 .3.gz .5 .5.gz .7 .7.gz .8 .8.gz .a .c .cxx .h .man .o .gz
+ 
+ .c.o:
diff --git a/package/cups/patches/patch-configure b/package/cups/patches/patch-configure
index 19c9f6092..3a4974140 100644
--- a/package/cups/patches/patch-configure
+++ b/package/cups/patches/patch-configure
@@ -1,11 +1,14 @@
 --- cups-1.7.1.orig/configure	2014-01-08 17:26:27.000000000 +0100
-+++ cups-1.7.1/configure	2014-01-24 18:05:03.000000000 +0100
-@@ -5792,7 +5792,7 @@ fi
++++ cups-1.7.1/configure	2014-01-31 16:48:50.000000000 +0100
+@@ -2490,9 +2490,8 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu
  
- case "$COMPONENTS" in
- 	all)
--		BUILDDIRS="filter backend berkeley cgi-bin monitor notifier ppdc scheduler systemv conf data desktop locale man doc examples templates"
-+		BUILDDIRS="filter backend berkeley monitor notifier ppdc conf data"
- 		;;
  
- 	core)
+ 
+-uname=`uname`
+-uversion=`uname -r | sed -e '1,$s/^[^0-9]*\([0-9]*\)\.\([0-9]*\).*/\1\2/'`
+-uarch=`uname -m`
++uname=Linux
++uversion=3.0
+ 
+ case "$uname" in
+ 	Darwin*)
diff --git a/package/firefox/Makefile b/package/firefox/Makefile
index 054541334..e4b69591d 100644
--- a/package/firefox/Makefile
+++ b/package/firefox/Makefile
@@ -30,6 +30,7 @@ DISTFILES:=             ${PKG_NAME}-${PKG_VERSION}.source.tar.bz2
 WRKDIST=		${WRKDIR}/mozilla-release
 
 include $(TOPDIR)/mk/package.mk
+include $(TOPDIR)/mk/python.mk
 
 $(eval $(call PKG_template,FIREFOX,firefox,$(PKG_VERSION)-${PKG_RELEASE},${PKG_DEPENDS},${PKG_DESCR},${PKG_SECTION}))
 
@@ -41,6 +42,7 @@ endif
 
 
 CONFIGURE_ENV+=		CROSS_COMPILE=1 \
+			PYTHON="$(PYTHON)" \
 			HOST_CC="${CC_FOR_BUILD}" \
 			HOST_CPPFLAGS="${CPPFLAGS_FOR_BUILD}" \
 			HOST_CFLAGS="${CFLAGS_FOR_BUILD}" \
diff --git a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
index bf6c335de..3a79329a3 100644
--- a/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
+++ b/package/firefox/patches/patch-media_mtransport_third_party_nICEr_src_stun_addrs_c
@@ -1,6 +1,6 @@
 --- mozilla-release.orig/media/mtransport/third_party/nICEr/src/stun/addrs.c	2013-12-05 17:07:48.000000000 +0100
-+++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c	2014-01-03 13:06:22.000000000 +0100
-@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id:
++++ mozilla-release/media/mtransport/third_party/nICEr/src/stun/addrs.c	2014-02-05 07:19:01.000000000 +0100
+@@ -53,7 +53,9 @@ static char *RCSSTRING __UNUSED__="$Id: 
  #undef __unused
  #include <linux/sysctl.h>
  #endif
@@ -10,7 +10,7 @@
  #ifndef LINUX
  #if !defined(__OpenBSD__) && !defined(__NetBSD__)
  #include <net/if_var.h>
-@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id:
+@@ -61,14 +63,17 @@ static char *RCSSTRING __UNUSED__="$Id: 
  #include <net/if_dl.h>
  #include <net/if_types.h>
  #include <sys/sockio.h>
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
new file mode 100644
index 000000000..60d33bb2e
--- /dev/null
+++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_common_py
@@ -0,0 +1,23 @@
+--- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py	2013-12-05 17:07:48.000000000 +0100
++++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/common.py	2014-02-05 08:12:49.000000000 +0100
+@@ -364,20 +364,6 @@ def WriteOnDiff(filename):
+ 
+ def GetFlavor(params):
+   """Returns |params.flavor| if it's set, the system's default flavor else."""
+-  flavors = {
+-    'cygwin': 'win',
+-    'win32': 'win',
+-    'darwin': 'mac',
+-  }
+-
+-  if 'flavor' in params:
+-    return params['flavor']
+-  if sys.platform in flavors:
+-    return flavors[sys.platform]
+-  if sys.platform.startswith('sunos'):
+-    return 'solaris'
+-  if sys.platform.startswith('freebsd'):
+-    return 'freebsd'
+ 
+   return 'linux'
+ 
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
new file mode 100644
index 000000000..452d380f0
--- /dev/null
+++ b/package/firefox/patches/patch-media_webrtc_trunk_tools_gyp_pylib_gyp_generator_mozmake_py
@@ -0,0 +1,26 @@
+--- mozilla-release.orig/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py	2013-12-05 17:07:48.000000000 +0100
++++ mozilla-release/media/webrtc/trunk/tools/gyp/pylib/gyp/generator/mozmake.py	2014-02-05 08:13:30.000000000 +0100
+@@ -118,23 +118,6 @@ def ensure_directory_exists(path):
+ 
+ def GetFlavor(params):
+   """Returns |params.flavor| if it's set, the system's default flavor else."""
+-  system = platform.system().lower()
+-  flavors = {
+-    'microsoft': 'win',
+-    'windows'  : 'win',
+-    'cygwin'   : 'win',
+-    'darwin'   : 'mac',
+-    'sunos'    : 'solaris',
+-    'dragonfly': 'dragonfly',
+-    'freebsd'  : 'freebsd',
+-    'netbsd'   : 'netbsd',
+-    'openbsd'  : 'openbsd',
+-  }
+-
+-  if 'flavor' in params:
+-    return params['flavor']
+-  if system in flavors:
+-    return flavors[system]
+ 
+   return 'linux'
+ 
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
index 3ee2e0fdc..809dff52a 100644
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
+++ b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_cpu_info_cc
@@ -1,6 +1,6 @@
 --- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2014-01-02 14:58:37.000000000 +0100
-@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
++++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/cpu_info.cc	2014-02-05 07:19:01.000000000 +0100
+@@ -36,11 +36,6 @@ uint32_t CpuInfo::DetectNumberOfCores() 
      WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1,
                   "Available number of cores:%d", number_of_cores_);
  
@@ -12,7 +12,7 @@
  #elif defined(WEBRTC_BSD) || defined(WEBRTC_MAC)
      int name[] = {
        CTL_HW,
-@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores()
+@@ -61,8 +56,6 @@ uint32_t CpuInfo::DetectNumberOfCores() 
                     "Failed to get number of cores");
        number_of_cores_ = 1;
      }
diff --git a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
index ac1d23267..95cfd56ba 100644
--- a/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
+++ b/package/firefox/patches/patch-media_webrtc_trunk_webrtc_system_wrappers_source_spreadsortlib_spreadsort_hpp
@@ -1,14 +1,3385 @@
 --- mozilla-release.orig/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2013-12-05 17:07:50.000000000 +0100
-+++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2014-01-02 14:53:44.000000000 +0100
-@@ -21,6 +21,11 @@ Scott McMurray
- #include <vector>
- #include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
- 
-+#include <features.h>
-+#if defined(__UCLIBC__)
-+#undef getchar
-+#endif
-+
- namespace boost {
-   namespace detail {
-   	//This only works on unsigned data types
++++ mozilla-release/media/webrtc/trunk/webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp	2014-02-05 09:52:11.000000000 +0100
+@@ -1,1688 +1,1694 @@
+-//Templated spread_sort library
+-
+-//          Copyright Steven J. Ross 2001 - 2009.
+-// Distributed under the Boost Software License, Version 1.0.
+-//    (See accompanying file LICENSE_1_0.txt or copy at
+-//          http://www.boost.org/LICENSE_1_0.txt)
+-
+-//  See http://www.boost.org/ for updates, documentation, and revision history.
+-		  
+-/*
+-Some improvements suggested by:
+-Phil Endecott and Frank Gennari
+-Cygwin fix provided by:
+-Scott McMurray
+-*/
+-
+-#ifndef BOOST_SPREAD_SORT_H
+-#define BOOST_SPREAD_SORT_H
+-#include <algorithm>
+-#include <cstring>
+-#include <vector>
+-#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
+-
+-namespace boost {
+-  namespace detail {
+-  	//This only works on unsigned data types
+-  	template <typename T>
+-  	inline unsigned 
+-  	rough_log_2_size(const T& input) 
+-  	{
+-  		unsigned result = 0;
+-  		//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
+-  		while((input >> result) && (result < (8*sizeof(T)))) ++result;
+-  		return result;
+-  	}
+-
+-  	//Gets the maximum size which we'll call spread_sort on to control worst-case performance
+-  	//Maintains both a minimum size to recurse and a check of distribution size versus count
+-  	//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
+-  	inline size_t
+-  	get_max_count(unsigned log_range, size_t count)
+-  	{
+-  		unsigned divisor = rough_log_2_size(count);
+-  		//Making sure the divisor is positive
+-  		if(divisor > LOG_MEAN_BIN_SIZE)
+-  			divisor -= LOG_MEAN_BIN_SIZE;
+-  		else
+-  			divisor = 1;
+-  		unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
+-  		//Don't try to bitshift more than the size of an element
+-  		if((8*sizeof(size_t)) <= relative_width)
+-  			relative_width = (8*sizeof(size_t)) - 1;
+-  		return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 
+-  			(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  relative_width);
+-  	}
+-
+-  	//Find the minimum and maximum using <
+-  	template <class RandomAccessIter>
+-  	inline void 
+-  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
+-  	{
+-  		min = max = current;
+-  		//Start from the second item, as max and min are initialized to the first
+-  		while(++current < last) {
+-  			if(*max < *current)
+-  				max = current;
+-  			else if(*current < *min)
+-  				min = current;
+-  		}
+-  	}
+-
+-  	//Uses a user-defined comparison operator to find minimum and maximum
+-  	template <class RandomAccessIter, class compare>
+-  	inline void 
+-  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
+-  	{
+-  		min = max = current;
+-  		while(++current < last) {
+-  			if(comp(*max, *current))
+-  				max = current;
+-  			else if(comp(*current, *min))
+-  				min = current;
+-  		}
+-  	}
+-
+-  	//Gets a non-negative right bit shift to operate as a logarithmic divisor
+-  	inline int
+-  	get_log_divisor(size_t count, unsigned log_range)
+-  	{
+-  		int log_divisor;
+-  		//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
+-  		if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
+-  			log_divisor = 0;
+-  		else {
+-  			//otherwise divide the data into an optimized number of pieces
+-  			log_divisor += LOG_MEAN_BIN_SIZE;
+-  			if(log_divisor < 0)
+-  				log_divisor = 0;
+-  			//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
+-  			if((log_range - log_divisor) > MAX_SPLITS)
+-  				log_divisor = log_range - MAX_SPLITS;
+-  		}
+-  		return log_divisor;
+-  	}
+-
+-  	template <class RandomAccessIter>
+-  	inline RandomAccessIter * 
+-  	size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
+-  	{
+-  		//Assure space for the size of each bin, followed by initializing sizes
+-  		if(bin_count > bin_sizes.size())
+-  			bin_sizes.resize(bin_count);
+-  		for(size_t u = 0; u < bin_count; u++)
+-  			bin_sizes[u] = 0;
+-  		//Make sure there is space for the bins
+-  		cache_end = cache_offset + bin_count;
+-  		if(cache_end > bin_cache.size())
+-  			bin_cache.resize(cache_end);
+-  		return &(bin_cache[cache_offset]);
+-  	}
+-
+-  	//Implementation for recursive integer sorting
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void 
+-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  				  , std::vector<size_t> &bin_sizes)
+-  	{
+-  		//This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
+-  		//If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
+-  		RandomAccessIter max, min;
+-  		find_extremes(first, last, max, min);
+-  		//max and min will be the same (the first item) iff all values are equivalent
+-  		if(max == min)
+-  			return;
+-  		RandomAccessIter * target_bin;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
+-  		div_type div_min = *min >> log_divisor;
+-  		div_type div_max = *max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  	
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[(*(current++) >> log_divisor) - div_min]++;
+-  		//Assign the bin positions
+-  		bins[0] = first;
+-  		for(unsigned u = 0; u < bin_count - 1; u++)
+-  			bins[u + 1] = bins[u] + bin_sizes[u];
+-  
+-  		//Swap into place
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count - 1; ++u) {
+-  			RandomAccessIter * local_bin = bins + u;
+-  			nextbinstart += bin_sizes[u];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = (bins + ((*current >> log_divisor) - div_min));  target_bin != local_bin; 
+-  					target_bin = bins + ((*current >> log_divisor) - div_min)) {
+-  					//3-way swap; this is about 1% faster than a 2-way swap with integers
+-  					//The main advantage is less copies are involved per item put in the correct place
+-  					data_type tmp;
+-  					RandomAccessIter b = (*target_bin)++;
+-  					RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
+-  					if (b_bin != local_bin) {
+-  						RandomAccessIter c = (*b_bin)++;
+-  						tmp = *c;
+-  						*c = *b;
+-  					} 
+-  					else
+-  						tmp = *b;
+-  					*b = *current;
+-  					*current = tmp;
+-  				}
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[bin_count - 1] = last;
+-  
+-  		//If we've bucketsorted, the array is sorted and we should skip recursion
+-  		if(!log_divisor)
+-  			return;
+-  
+-  		//Recursing; log_divisor is the remaining range
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			else
+-  				spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//Generic bitshift-based 3-way swapping code
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+-  		, const unsigned log_divisor, const div_type div_min) 
+-  	{
+-  		RandomAccessIter * local_bin = bins + ii;
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min));  target_bin != local_bin; 
+-  				target_bin = bins + (shift(*current, log_divisor) - div_min)) {
+-  				data_type tmp;
+-  				RandomAccessIter b = (*target_bin)++;
+-  				RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
+-  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+-  				if (b_bin != local_bin) {
+-  					RandomAccessIter c = (*b_bin)++;
+-  					tmp = *c;
+-  					*c = *b;
+-  				} 
+-  				//Note: we could increment current once the swap is done in this case, but that seems to impair performance
+-  				else
+-  					tmp = *b;
+-  				*b = *current;
+-  				*current = tmp;
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  	}
+-
+-  	//Standard swapping wrapper for ascending values
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+-  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
+-  	{
+-  		nextbinstart += bin_sizes[ii];
+-  		inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
+-  	}
+-
+-  	//Functor implementation for recursive sorting
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+-  	inline void 
+-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+-  	{
+-  		RandomAccessIter max, min;
+-  		find_extremes(first, last, max, min, comp);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+-  		div_type div_min = shift(*min, log_divisor);
+-  		div_type div_max = shift(*max, log_divisor);
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		bins[0] = first;
+-  		for(unsigned u = 0; u < bin_count - 1; u++)
+-  			bins[u + 1] = bins[u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count - 1; ++u)
+-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
+-  		bins[bin_count - 1] = last;
+-  		
+-  		//If we've bucketsorted, the array is sorted and we should skip recursion
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u], comp);
+-  			else
+-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+-  		}
+-  	}
+-
+-  	//Functor implementation for recursive sorting with only Shift overridden
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void 
+-  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift)
+-  	{
+-  		RandomAccessIter max, min;
+-  		find_extremes(first, last, max, min);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+-  		div_type div_min = shift(*min, log_divisor);
+-  		div_type div_max = shift(*max, log_divisor);
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		bins[0] = first;
+-  		for(unsigned u = 0; u < bin_count - 1; u++)
+-  			bins[u + 1] = bins[u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned ii = 0; ii < bin_count - 1; ++ii)
+-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+-  		bins[bin_count - 1] = last;
+-  		
+-  		//If we've bucketsorted, the array is sorted and we should skip recursion
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			else
+-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+-  		}
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void 
+-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+-  	inline void 
+-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void 
+-  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+-  	}
+-  }
+-
+-  //Top-level sorting call for integers
+-  template <class RandomAccessIter>
+-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else
+-  		detail::spread_sort(first, last, *first >> 0, *first);
+-  }
+-
+-  //integer_sort with functors
+-  template <class RandomAccessIter, class right_shift, class compare>
+-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+-  						right_shift shift, compare comp) {
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last, comp);
+-  	else
+-  		detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
+-  }
+-
+-  //integer_sort with right_shift functor
+-  template <class RandomAccessIter, class right_shift>
+-  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+-  						right_shift shift) {
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else
+-  		detail::spread_sort(first, last, shift(*first, 0), *first, shift);
+-  }
+-
+-  //------------------------------------------------------ float_sort source --------------------------------------
+-  //Casts a RandomAccessIter to the specified data type
+-  template<class cast_type, class RandomAccessIter>
+-  inline cast_type
+-  cast_float_iter(const RandomAccessIter & floatiter)
+-  {
+-  	cast_type result;
+-  	std::memcpy(&result, &(*floatiter), sizeof(cast_type));
+-  	return result;
+-  }
+-
+-  //Casts a data element to the specified datinner_float_a type
+-  template<class data_type, class cast_type>
+-  inline cast_type
+-  mem_cast(const data_type & data)
+-  {
+-  	cast_type result;
+-  	std::memcpy(&result, &data, sizeof(cast_type));
+-  	return result;
+-  }
+-
+-  namespace detail {
+-  	template <class RandomAccessIter, class div_type, class right_shift>
+-  	inline void 
+-  	find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
+-  	{
+-  		min = max = shift(*current, 0);
+-  		while(++current < last) {
+-  			div_type value = shift(*current, 0);
+-  			if(max < value)
+-  				max = value;
+-  			else if(value < min)
+-  				min = value;
+-  		}
+-  	}
+-
+-  	//Specialized swap loops for floating-point casting
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
+-  		, const unsigned log_divisor, const div_type div_min) 
+-  	{
+-  		RandomAccessIter * local_bin = bins + ii;
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min));  target_bin != local_bin; 
+-  				target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
+-  				data_type tmp;
+-  				RandomAccessIter b = (*target_bin)++;
+-  				RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
+-  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+-  				if (b_bin != local_bin) {
+-  					RandomAccessIter c = (*b_bin)++;
+-  					tmp = *c;
+-  					*c = *b;
+-  				} 
+-  				else
+-  					tmp = *b;
+-  				*b = *current;
+-  				*current = tmp;
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
+-  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
+-  	{
+-  		nextbinstart += bin_sizes[ii];
+-  		inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
+-  	}
+-
+-  	template <class RandomAccessIter, class cast_type>
+-  	inline void 
+-  	find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
+-  	{
+-  		min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
+-  		while(++current < last) {
+-  			cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
+-  			if(max < value)
+-  				max = value;
+-  			else if(value < min)
+-  				min = value;
+-  		}
+-  	}
+-
+-  	//Special-case sorting of positive floats with casting instead of a right_shift
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void 
+-  	positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+-  		bins[0] = first;
+-  		for(unsigned u = 0; u < bin_count - 1; u++)
+-  			bins[u + 1] = bins[u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count - 1; ++u)
+-  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
+-  		bins[bin_count - 1] = last;
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			else
+-  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//Sorting negative_ float_s
+-  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void 
+-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+-  		bins[bin_count - 1] = first;
+-  		for(int ii = bin_count - 2; ii >= 0; --ii)
+-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//The last bin will always have the correct elements in it
+-  		for(int ii = bin_count - 1; ii > 0; --ii)
+-  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
+-  		//Since we don't process the last bin, we need to update its end position
+-  		bin_cache[cache_offset] = last;
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii]);
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//Sorting negative_ float_s
+-  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void 
+-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min, shift);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		bins[bin_count - 1] = first;
+-  		for(int ii = bin_count - 2; ii >= 0; --ii)
+-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//The last bin will always have the correct elements in it
+-  		for(int ii = bin_count - 1; ii > 0; --ii)
+-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+-  		//Since we don't process the last bin, we need to update its end position
+-  		bin_cache[cache_offset] = last;
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii]);
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+-  		}
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+-  	inline void 
+-  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min, shift);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		bins[bin_count - 1] = first;
+-  		for(int ii = bin_count - 2; ii >= 0; --ii)
+-  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//The last bin will always have the correct elements in it
+-  		for(int ii = bin_count - 1; ii > 0; --ii)
+-  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+-  		//Since we don't process the last bin, we need to update its end position
+-  		bin_cache[cache_offset] = last;
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Recursing
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii], comp);
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+-  		}
+-  	}
+-
+-  	//Casting special-case for floating-point sorting
+-  	template <class RandomAccessIter, class div_type, class data_type>
+-  	inline void 
+-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+-  		//The index of the first positive bin
+-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+-  		//Resetting if all bins are negative
+-  		if(cache_offset + first_positive > cache_end)
+-  			first_positive = cache_end - cache_offset;
+-  		//Reversing the order of the negative bins
+-  		//Note that because of the negative/positive ordering direction flip
+-  		//We can not depend upon bin order and positions matching up
+-  		//so bin_sizes must be reused to contain the end of the bin
+-  		if(first_positive > 0) {
+-  			bins[first_positive - 1] = first;
+-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+-  				bins[ii] = first + bin_sizes[ii + 1];
+-  				bin_sizes[ii] += bin_sizes[ii + 1];
+-  			}
+-  			//Handling positives following negatives
+-  			if((unsigned)first_positive < bin_count) {
+-  				bins[first_positive] = first + bin_sizes[0];
+-  				bin_sizes[first_positive] += bin_sizes[0];
+-  			}
+-  		}
+-  		else
+-  			bins[0] = first;
+-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+-  			bins[u + 1] = first + bin_sizes[u];
+-  			bin_sizes[u + 1] += bin_sizes[u];
+-  		}
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count; ++u) {
+-  			nextbinstart = first + bin_sizes[u];
+-  			inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
+-  		}
+-  		
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Handling negative values first
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii]);
+-  			//sort negative values using reversed-bin spread_sort
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+-  		}
+-  		
+-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			//sort positive values using normal spread_sort
+-  			else
+-  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//Functor implementation for recursive sorting
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void 
+-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min, shift);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		//The index of the first positive bin
+-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+-  		//Resetting if all bins are negative
+-  		if(cache_offset + first_positive > cache_end)
+-  			first_positive = cache_end - cache_offset;
+-  		//Reversing the order of the negative bins
+-  		//Note that because of the negative/positive ordering direction flip
+-  		//We can not depend upon bin order and positions matching up
+-  		//so bin_sizes must be reused to contain the end of the bin
+-  		if(first_positive > 0) {
+-  			bins[first_positive - 1] = first;
+-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+-  				bins[ii] = first + bin_sizes[ii + 1];
+-  				bin_sizes[ii] += bin_sizes[ii + 1];
+-  			}
+-  			//Handling positives following negatives
+-  			if((unsigned)first_positive < bin_count) {
+-  				bins[first_positive] = first + bin_sizes[0];
+-  				bin_sizes[first_positive] += bin_sizes[0];
+-  			}
+-  		}
+-  		else
+-  			bins[0] = first;
+-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+-  			bins[u + 1] = first + bin_sizes[u];
+-  			bin_sizes[u + 1] += bin_sizes[u];
+-  		}
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count; ++u) {
+-  			nextbinstart = first + bin_sizes[u];
+-  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+-  		}
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Handling negative values first
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii]);
+-  			//sort negative values using reversed-bin spread_sort
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+-  		}
+-  		
+-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			//sort positive values using normal spread_sort
+-  			else
+-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+-  		}
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+-  	inline void 
+-  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+-  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+-  	{
+-  		div_type max, min;
+-  		find_extremes(first, last, max, min, shift);
+-  		if(max == min)
+-  			return;
+-  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+-  		div_type div_min = min >> log_divisor;
+-  		div_type div_max = max >> log_divisor;
+-  		unsigned bin_count = div_max - div_min + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+-  			
+-  		//Calculating the size of each bin
+-  		for (RandomAccessIter current = first; current != last;)
+-  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+-  		//The index of the first positive bin
+-  		div_type first_positive = (div_min < 0) ? -div_min : 0;
+-  		//Resetting if all bins are negative
+-  		if(cache_offset + first_positive > cache_end)
+-  			first_positive = cache_end - cache_offset;
+-  		//Reversing the order of the negative bins
+-  		//Note that because of the negative/positive ordering direction flip
+-  		//We can not depend upon bin order and positions matching up
+-  		//so bin_sizes must be reused to contain the end of the bin
+-  		if(first_positive > 0) {
+-  			bins[first_positive - 1] = first;
+-  			for(int ii = first_positive - 2; ii >= 0; --ii) {
+-  				bins[ii] = first + bin_sizes[ii + 1];
+-  				bin_sizes[ii] += bin_sizes[ii + 1];
+-  			}
+-  			//Handling positives following negatives
+-  			if((unsigned)first_positive < bin_count) {
+-  				bins[first_positive] = first + bin_sizes[0];
+-  				bin_sizes[first_positive] += bin_sizes[0];
+-  			}
+-  		}
+-  		else
+-  			bins[0] = first;
+-  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
+-  			bins[u + 1] = first + bin_sizes[u];
+-  			bin_sizes[u + 1] += bin_sizes[u];
+-  		}
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		for(unsigned u = 0; u < bin_count; ++u) {
+-  			nextbinstart = first + bin_sizes[u];
+-  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+-  		}
+-  		
+-  		//Return if we've completed bucketsorting
+-  		if(!log_divisor)
+-  			return;
+-  		
+-  		//Handling negative values first
+-  		size_t max_count = get_max_count(log_divisor, last - first);
+-  		RandomAccessIter lastPos = first;
+-  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+-  			size_t count = bin_cache[ii] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[ii]);
+-  			//sort negative values using reversed-bin spread_sort
+-  			else
+-  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+-  		}
+-  		
+-  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			if(count < 2)
+-  				continue;
+-  			if(count < max_count)
+-  				std::sort(lastPos, bin_cache[u]);
+-  			//sort positive values using normal spread_sort
+-  			else
+-  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+-  		}
+-  	}
+-
+-  	template <class RandomAccessIter, class cast_type, class data_type>
+-  	inline void 
+-  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+-  	inline void 
+-  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+-  	}
+-
+-  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+-  	inline void 
+-  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+-  	}
+-  }
+-
+-  //float_sort with casting
+-  //The cast_type must be equal in size to the data type, and must be a signed integer
+-  template <class RandomAccessIter, class cast_type>
+-  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 
+-  {
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else
+-  		detail::float_Sort(first, last, cVal, *first);
+-  }
+-
+-  //float_sort with casting to an int
+-  //Only use this with IEEE floating-point numbers
+-  template <class RandomAccessIter>
+-  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 
+-  {
+-  	int cVal = 0;
+-  	float_sort_cast(first, last, cVal);
+-  }
+-
+-  //float_sort with functors
+-  template <class RandomAccessIter, class right_shift>
+-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 
+-  {
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else
+-  		detail::float_Sort(first, last, shift(*first, 0), *first, shift);
+-  }
+-
+-  template <class RandomAccessIter, class right_shift, class compare>
+-  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 
+-  {
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last, comp);
+-  	else
+-  		detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
+-  }
+-
+-  //------------------------------------------------- string_sort source ---------------------------------------------
+-  namespace detail {
+-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
+-  	template<class RandomAccessIter>
+-  	inline void
+-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
+-  	{
+-  		unsigned nextOffset = char_offset;
+-  		bool done = false;
+-  		while(!done) {
+-  			RandomAccessIter curr = first;
+-  			do {
+-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+-  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
+-  					done = true;
+-  					break;
+-  				}
+-  			} while(++curr != finish);
+-  			if(!done)
+-  				++nextOffset;
+-  		} 
+-  		char_offset = nextOffset;
+-  	}
+-
+-  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
+-  	template<class RandomAccessIter, class get_char, class get_length>
+-  	inline void
+-  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
+-  	{
+-  		unsigned nextOffset = char_offset;
+-  		bool done = false;
+-  		while(!done) {
+-  			RandomAccessIter curr = first;
+-  			do {
+-  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+-  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
+-  					done = true;
+-  					break;
+-  				}
+-  			} while(++curr != finish);
+-  			if(!done)
+-  				++nextOffset;
+-  		} 
+-  		char_offset = nextOffset;
+-  	}
+-
+-  	//A comparison functor for strings that assumes they are identical up to char_offset
+-  	template<class data_type, class unsignedchar_type>
+-  	struct offset_lessthan {
+-  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+-  		inline bool operator()(const data_type &x, const data_type &y) const 
+-  		{
+-  			unsigned minSize = std::min(x.size(), y.size());
+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+-  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
+-  					return true;
+-  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
+-  					return false;
+-  			}
+-  			return x.size() < y.size();
+-  		}
+-  		unsigned fchar_offset;
+-  	};
+-
+-  	//A comparison functor for strings that assumes they are identical up to char_offset
+-  	template<class data_type, class unsignedchar_type>
+-  	struct offset_greaterthan {
+-  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
+-  		inline bool operator()(const data_type &x, const data_type &y) const 
+-  		{
+-  			unsigned minSize = std::min(x.size(), y.size());
+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+-  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
+-  					return true;
+-  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
+-  					return false;
+-  			}
+-  			return x.size() > y.size();
+-  		}
+-  		unsigned fchar_offset;
+-  	};
+-
+-  	//A comparison functor for strings that assumes they are identical up to char_offset
+-  	template<class data_type, class get_char, class get_length>
+-  	struct offset_char_lessthan {
+-  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+-  		inline bool operator()(const data_type &x, const data_type &y) const 
+-  		{
+-  			unsigned minSize = std::min(length(x), length(y));
+-  			for(unsigned u = fchar_offset; u < minSize; ++u) {
+-  				if(getchar(x, u) < getchar(y, u))
+-  					return true;
+-  				else if(getchar(y, u) < getchar(x, u))
+-  					return false;
+-  			}
+-  			return length(x) < length(y);
+-  		}
+-  		unsigned fchar_offset;
+-  		get_char getchar;
+-  		get_length length;
+-  	};
+-
+-  	//String sorting recursive implementation
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
+-  	{
+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+-  		//Iterate to the end of the empties.  If all empty, return
+-  		while((*first).size() <= char_offset) {
+-  			if(++first == last)
+-  				return;
+-  		}
+-  		RandomAccessIter finish = last - 1;
+-  		//Getting the last non-empty
+-  		for(;(*finish).size() <= char_offset; --finish) { }
+-  		++finish;
+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+-  		update_offset(first, finish, char_offset);
+-  		
+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+-  		const unsigned max_size = bin_count;
+-  		const unsigned membin_count = bin_count + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+-  			
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last; ++current) {
+-  			if((*current).size() <= char_offset) {
+-  				bin_sizes[0]++;
+-  			}
+-  			else
+-  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
+-  		}
+-  		//Assign the bin positions
+-  		bin_cache[cache_offset] = first;
+-  		for(unsigned u = 0; u < membin_count - 1; u++)
+-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//handling empty bins
+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+-  		nextbinstart +=	bin_sizes[0];
+-  		RandomAccessIter * target_bin;
+-  		//Iterating over each element in the bin of empties
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			//empties belong in this bin
+-  			while((*current).size() > char_offset) {
+-  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
+-  				iter_swap(current, (*target_bin)++);
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+-  		unsigned last_bin = bin_count - 1;
+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		for(unsigned u = 0; u < last_bin; ++u) {
+-  			local_bin = bins + u;
+-  			nextbinstart += bin_sizes[u + 1];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
+-  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
+-  					iter_swap(current, (*target_bin)++);
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[last_bin] = last;
+-  		//Recursing
+-  		RandomAccessIter lastPos = bin_cache[cache_offset];
+-  		//Skip this loop for empties
+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_size)
+-  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
+-  			else
+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//Sorts strings in reverse order, with empties at the end
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
+-  	{
+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+-  		RandomAccessIter curr = first;
+-  		//Iterate to the end of the empties.  If all empty, return
+-  		while((*curr).size() <= char_offset) {
+-  			if(++curr == last)
+-  				return;
+-  		}
+-  		//Getting the last non-empty
+-  		while((*(--last)).size() <= char_offset) { }
+-  		++last;
+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+-  		update_offset(curr, last, char_offset);
+-  		RandomAccessIter * target_bin;
+-  		
+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+-  		const unsigned max_size = bin_count;
+-  		const unsigned membin_count = bin_count + 1;
+-  		const unsigned max_bin = bin_count - 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+-  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
+-  			
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last; ++current) {
+-  			if((*current).size() <= char_offset) {
+-  				bin_sizes[bin_count]++;
+-  			}
+-  			else
+-  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
+-  		}
+-  		//Assign the bin positions
+-  		bin_cache[cache_offset] = first;
+-  		for(unsigned u = 0; u < membin_count - 1; u++)
+-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = last;
+-  		//handling empty bins
+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+-  		RandomAccessIter lastFull = *local_bin;
+-  		//Iterating over each element in the bin of empties
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			//empties belong in this bin
+-  			while((*current).size() > char_offset) {
+-  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
+-  				iter_swap(current, (*target_bin)++);
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  		nextbinstart = first;
+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+-  		unsigned last_bin = max_bin;
+-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		for(unsigned u = 0; u < last_bin; ++u) {
+-  			local_bin = bins + u;
+-  			nextbinstart += bin_sizes[u];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
+-  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
+-  					iter_swap(current, (*target_bin)++);
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[last_bin] = lastFull;
+-  		//Recursing
+-  		RandomAccessIter lastPos = first;
+-  		//Skip this loop for empties
+-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_size)
+-  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
+-  			else
+-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+-  		}
+-  	}
+-
+-  	//String sorting recursive implementation
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
+-  	inline void 
+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
+-  	{
+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+-  		//Iterate to the end of the empties.  If all empty, return
+-  		while(length(*first) <= char_offset) {
+-  			if(++first == last)
+-  				return;
+-  		}
+-  		RandomAccessIter finish = last - 1;
+-  		//Getting the last non-empty
+-  		for(;length(*finish) <= char_offset; --finish) { }
+-  		++finish;
+-  		update_offset(first, finish, char_offset, getchar, length);
+-  		
+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+-  		const unsigned max_size = bin_count;
+-  		const unsigned membin_count = bin_count + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+-  			
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last; ++current) {
+-  			if(length(*current) <= char_offset) {
+-  				bin_sizes[0]++;
+-  			}
+-  			else
+-  				bin_sizes[getchar((*current), char_offset) + 1]++;
+-  		}
+-  		//Assign the bin positions
+-  		bin_cache[cache_offset] = first;
+-  		for(unsigned u = 0; u < membin_count - 1; u++)
+-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//handling empty bins
+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+-  		nextbinstart +=	bin_sizes[0];
+-  		RandomAccessIter * target_bin;
+-  		//Iterating over each element in the bin of empties
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			//empties belong in this bin
+-  			while(length(*current) > char_offset) {
+-  				target_bin = bins + getchar((*current), char_offset);
+-  				iter_swap(current, (*target_bin)++);
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+-  		unsigned last_bin = bin_count - 1;
+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		for(unsigned ii = 0; ii < last_bin; ++ii) {
+-  			local_bin = bins + ii;
+-  			nextbinstart += bin_sizes[ii + 1];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
+-  					target_bin = bins + getchar((*current), char_offset))
+-  					iter_swap(current, (*target_bin)++);
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[last_bin] = last;
+-  		
+-  		//Recursing
+-  		RandomAccessIter lastPos = bin_cache[cache_offset];
+-  		//Skip this loop for empties
+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_size)
+-  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
+-  			else
+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
+-  		}
+-  	}
+-
+-  	//String sorting recursive implementation
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+-  	inline void 
+-  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+-  	{
+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+-  		//Iterate to the end of the empties.  If all empty, return
+-  		while(length(*first) <= char_offset) {
+-  			if(++first == last)
+-  				return;
+-  		}
+-  		RandomAccessIter finish = last - 1;
+-  		//Getting the last non-empty
+-  		for(;length(*finish) <= char_offset; --finish) { }
+-  		++finish;
+-  		update_offset(first, finish, char_offset, getchar, length);
+-  		
+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+-  		const unsigned max_size = bin_count;
+-  		const unsigned membin_count = bin_count + 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+-  			
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last; ++current) {
+-  			if(length(*current) <= char_offset) {
+-  				bin_sizes[0]++;
+-  			}
+-  			else
+-  				bin_sizes[getchar((*current), char_offset) + 1]++;
+-  		}
+-  		//Assign the bin positions
+-  		bin_cache[cache_offset] = first;
+-  		for(unsigned u = 0; u < membin_count - 1; u++)
+-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = first;
+-  		//handling empty bins
+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+-  		nextbinstart +=	bin_sizes[0];
+-  		RandomAccessIter * target_bin;
+-  		//Iterating over each element in the bin of empties
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			//empties belong in this bin
+-  			while(length(*current) > char_offset) {
+-  				target_bin = bins + getchar((*current), char_offset);
+-  				iter_swap(current, (*target_bin)++);
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+-  		unsigned last_bin = bin_count - 1;
+-  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		for(unsigned u = 0; u < last_bin; ++u) {
+-  			local_bin = bins + u;
+-  			nextbinstart += bin_sizes[u + 1];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
+-  					target_bin = bins + getchar((*current), char_offset))
+-  					iter_swap(current, (*target_bin)++);
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[last_bin] = last;
+-  		
+-  		//Recursing
+-  		RandomAccessIter lastPos = bin_cache[cache_offset];
+-  		//Skip this loop for empties
+-  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_size)
+-  				std::sort(lastPos, bin_cache[u], comp);
+-  			else
+-  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+-  		}
+-  	}
+-
+-  	//Sorts strings in reverse order, with empties at the end
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+-  	inline void 
+-  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+-  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+-  	{
+-  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+-  		RandomAccessIter curr = first;
+-  		//Iterate to the end of the empties.  If all empty, return
+-  		while(length(*curr) <= char_offset) {
+-  			if(++curr == last)
+-  				return;
+-  		}
+-  		//Getting the last non-empty
+-  		while(length(*(--last)) <= char_offset) { }
+-  		++last;
+-  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
+-  		update_offset(first, last, char_offset, getchar, length);
+-  		
+-  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+-  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+-  		const unsigned max_size = bin_count;
+-  		const unsigned membin_count = bin_count + 1;
+-  		const unsigned max_bin = bin_count - 1;
+-  		unsigned cache_end;
+-  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+-  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
+-  			
+-  		//Calculating the size of each bin; this takes roughly 10% of runtime
+-  		for (RandomAccessIter current = first; current != last; ++current) {
+-  			if(length(*current) <= char_offset) {
+-  				bin_sizes[bin_count]++;
+-  			}
+-  			else
+-  				bin_sizes[max_bin - getchar((*current), char_offset)]++;
+-  		}
+-  		//Assign the bin positions
+-  		bin_cache[cache_offset] = first;
+-  		for(unsigned u = 0; u < membin_count - 1; u++)
+-  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+-  		
+-  		//Swap into place
+-  		RandomAccessIter nextbinstart = last;
+-  		//handling empty bins
+-  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+-  		RandomAccessIter lastFull = *local_bin;
+-  		RandomAccessIter * target_bin;
+-  		//Iterating over each element in the bin of empties
+-  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  			//empties belong in this bin
+-  			while(length(*current) > char_offset) {
+-  				target_bin = end_bin - getchar((*current), char_offset);
+-  				iter_swap(current, (*target_bin)++);
+-  			}
+-  		}
+-  		*local_bin = nextbinstart;
+-  		nextbinstart = first;
+-  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+-  		unsigned last_bin = max_bin;
+-  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+-  		//This dominates runtime, mostly in the swap and bin lookups
+-  		for(unsigned u = 0; u < last_bin; ++u) {
+-  			local_bin = bins + u;
+-  			nextbinstart += bin_sizes[u];
+-  			//Iterating over each element in this bin
+-  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+-  				//Swapping elements in current into place until the correct element has been swapped in
+-  				for(target_bin = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 
+-  					target_bin = end_bin - getchar((*current), char_offset))
+-  					iter_swap(current, (*target_bin)++);
+-  			}
+-  			*local_bin = nextbinstart;
+-  		}
+-  		bins[last_bin] = lastFull;
+-  		//Recursing
+-  		RandomAccessIter lastPos = first;
+-  		//Skip this loop for empties
+-  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+-  			size_t count = bin_cache[u] - lastPos;
+-  			//don't sort unless there are at least two items to compare
+-  			if(count < 2)
+-  				continue;
+-  			//using std::sort if its worst-case is better
+-  			if(count < max_size)
+-  				std::sort(lastPos, bin_cache[u], comp);
+-  			else
+-  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+-  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+-  		}
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+-  	}
+-
+-  	//Holds the bin vector and makes the initial recursive call
+-  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+-  	inline void 
+-  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+-  	{
+-  		std::vector<size_t> bin_sizes;
+-  		std::vector<RandomAccessIter> bin_cache;
+-  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+-  	}
+-  }
+-
+-  //Allows character-type overloads
+-  template <class RandomAccessIter, class unsignedchar_type>
+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else
+-  		detail::string_sort(first, last, *first, unused);
+-  }
+-
+-  //Top-level sorting call; wraps using default of unsigned char
+-  template <class RandomAccessIter>
+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 
+-  {
+-  	unsigned char unused = '\0';
+-  	string_sort(first, last, unused);
+-  }
+-
+-  //Allows character-type overloads
+-  template <class RandomAccessIter, class compare, class unsignedchar_type>
+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last, comp);
+-  	else
+-  		detail::reverse_string_sort(first, last, *first, unused);
+-  }
+-
+-  //Top-level sorting call; wraps using default of unsigned char
+-  template <class RandomAccessIter, class compare>
+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 
+-  {
+-  	unsigned char unused = '\0';
+-  	reverse_string_sort(first, last, comp, unused);
+-  }
+-
+-  template <class RandomAccessIter, class get_char, class get_length>
+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last);
+-  	else {
+-  		//skipping past empties at the beginning, which allows us to get the character type 
+-  		//.empty() is not used so as not to require a user declaration of it
+-  		while(!length(*first)) {
+-  			if(++first == last)
+-  				return;
+-  		}
+-  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
+-  	}
+-  }
+-
+-  template <class RandomAccessIter, class get_char, class get_length, class compare>
+-  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last, comp);
+-  	else {
+-  		//skipping past empties at the beginning, which allows us to get the character type 
+-  		//.empty() is not used so as not to require a user declaration of it
+-  		while(!length(*first)) {
+-  			if(++first == last)
+-  				return;
+-  		}
+-  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+-  	}
+-  }
+-
+-  template <class RandomAccessIter, class get_char, class get_length, class compare>
+-  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
+-  {
+-  	//Don't sort if it's too small to optimize
+-  	if(last - first < detail::MIN_SORT_SIZE)
+-  		std::sort(first, last, comp);
+-  	else {
+-  		//skipping past empties at the beginning, which allows us to get the character type 
+-  		//.empty() is not used so as not to require a user declaration of it
+-  		while(!length(*(--last))) {
+-  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
+-  			if(first == last)
+-  				return;
+-  		}
+-  		//making last just after the end of the non-empty part of the array
+-  		++last;
+-  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+-  	}
+-  }
+-}
+-
+-#endif
++//Templated spread_sort library
++
++//          Copyright Steven J. Ross 2001 - 2009.
++// Distributed under the Boost Software License, Version 1.0.
++//    (See accompanying file LICENSE_1_0.txt or copy at
++//          http://www.boost.org/LICENSE_1_0.txt)
++
++//  See http://www.boost.org/ for updates, documentation, and revision history.
++		  
++/*
++Some improvements suggested by:
++Phil Endecott and Frank Gennari
++Cygwin fix provided by:
++Scott McMurray
++*/
++
++#ifndef BOOST_SPREAD_SORT_H
++#define BOOST_SPREAD_SORT_H
++#include <algorithm>
++#include <cstring>
++#include <vector>
++#include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"
++
++#include <features.h>
++#if defined(__UCLIBC__)
++#undef getchar
++#endif
++
++
++namespace boost {
++  namespace detail {
++  	//This only works on unsigned data types
++  	template <typename T>
++  	inline unsigned 
++  	rough_log_2_size(const T& input) 
++  	{
++  		unsigned result = 0;
++  		//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
++  		while((input >> result) && (result < (8*sizeof(T)))) ++result;
++  		return result;
++  	}
++
++  	//Gets the maximum size which we'll call spread_sort on to control worst-case performance
++  	//Maintains both a minimum size to recurse and a check of distribution size versus count
++  	//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
++  	inline size_t
++  	get_max_count(unsigned log_range, size_t count)
++  	{
++  		unsigned divisor = rough_log_2_size(count);
++  		//Making sure the divisor is positive
++  		if(divisor > LOG_MEAN_BIN_SIZE)
++  			divisor -= LOG_MEAN_BIN_SIZE;
++  		else
++  			divisor = 1;
++  		unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
++  		//Don't try to bitshift more than the size of an element
++  		if((8*sizeof(size_t)) <= relative_width)
++  			relative_width = (8*sizeof(size_t)) - 1;
++  		return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 
++  			(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  relative_width);
++  	}
++
++  	//Find the minimum and maximum using <
++  	template <class RandomAccessIter>
++  	inline void 
++  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
++  	{
++  		min = max = current;
++  		//Start from the second item, as max and min are initialized to the first
++  		while(++current < last) {
++  			if(*max < *current)
++  				max = current;
++  			else if(*current < *min)
++  				min = current;
++  		}
++  	}
++
++  	//Uses a user-defined comparison operator to find minimum and maximum
++  	template <class RandomAccessIter, class compare>
++  	inline void 
++  	find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
++  	{
++  		min = max = current;
++  		while(++current < last) {
++  			if(comp(*max, *current))
++  				max = current;
++  			else if(comp(*current, *min))
++  				min = current;
++  		}
++  	}
++
++  	//Gets a non-negative right bit shift to operate as a logarithmic divisor
++  	inline int
++  	get_log_divisor(size_t count, unsigned log_range)
++  	{
++  		int log_divisor;
++  		//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
++  		if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
++  			log_divisor = 0;
++  		else {
++  			//otherwise divide the data into an optimized number of pieces
++  			log_divisor += LOG_MEAN_BIN_SIZE;
++  			if(log_divisor < 0)
++  				log_divisor = 0;
++  			//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
++  			if((log_range - log_divisor) > MAX_SPLITS)
++  				log_divisor = log_range - MAX_SPLITS;
++  		}
++  		return log_divisor;
++  	}
++
++  	template <class RandomAccessIter>
++  	inline RandomAccessIter * 
++  	size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
++  	{
++  		//Assure space for the size of each bin, followed by initializing sizes
++  		if(bin_count > bin_sizes.size())
++  			bin_sizes.resize(bin_count);
++  		for(size_t u = 0; u < bin_count; u++)
++  			bin_sizes[u] = 0;
++  		//Make sure there is space for the bins
++  		cache_end = cache_offset + bin_count;
++  		if(cache_end > bin_cache.size())
++  			bin_cache.resize(cache_end);
++  		return &(bin_cache[cache_offset]);
++  	}
++
++  	//Implementation for recursive integer sorting
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void 
++  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  				  , std::vector<size_t> &bin_sizes)
++  	{
++  		//This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
++  		//If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
++  		RandomAccessIter max, min;
++  		find_extremes(first, last, max, min);
++  		//max and min will be the same (the first item) iff all values are equivalent
++  		if(max == min)
++  			return;
++  		RandomAccessIter * target_bin;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
++  		div_type div_min = *min >> log_divisor;
++  		div_type div_max = *max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  	
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[(*(current++) >> log_divisor) - div_min]++;
++  		//Assign the bin positions
++  		bins[0] = first;
++  		for(unsigned u = 0; u < bin_count - 1; u++)
++  			bins[u + 1] = bins[u] + bin_sizes[u];
++  
++  		//Swap into place
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count - 1; ++u) {
++  			RandomAccessIter * local_bin = bins + u;
++  			nextbinstart += bin_sizes[u];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = (bins + ((*current >> log_divisor) - div_min));  target_bin != local_bin; 
++  					target_bin = bins + ((*current >> log_divisor) - div_min)) {
++  					//3-way swap; this is about 1% faster than a 2-way swap with integers
++  					//The main advantage is less copies are involved per item put in the correct place
++  					data_type tmp;
++  					RandomAccessIter b = (*target_bin)++;
++  					RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
++  					if (b_bin != local_bin) {
++  						RandomAccessIter c = (*b_bin)++;
++  						tmp = *c;
++  						*c = *b;
++  					} 
++  					else
++  						tmp = *b;
++  					*b = *current;
++  					*current = tmp;
++  				}
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[bin_count - 1] = last;
++  
++  		//If we've bucketsorted, the array is sorted and we should skip recursion
++  		if(!log_divisor)
++  			return;
++  
++  		//Recursing; log_divisor is the remaining range
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			else
++  				spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Generic bitshift-based 3-way swapping code
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
++  		, const unsigned log_divisor, const div_type div_min) 
++  	{
++  		RandomAccessIter * local_bin = bins + ii;
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min));  target_bin != local_bin; 
++  				target_bin = bins + (shift(*current, log_divisor) - div_min)) {
++  				data_type tmp;
++  				RandomAccessIter b = (*target_bin)++;
++  				RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
++  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
++  				if (b_bin != local_bin) {
++  					RandomAccessIter c = (*b_bin)++;
++  					tmp = *c;
++  					*c = *b;
++  				} 
++  				//Note: we could increment current once the swap is done in this case, but that seems to impair performance
++  				else
++  					tmp = *b;
++  				*b = *current;
++  				*current = tmp;
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  	}
++
++  	//Standard swapping wrapper for ascending values
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
++  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
++  	{
++  		nextbinstart += bin_sizes[ii];
++  		inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
++  	}
++
++  	//Functor implementation for recursive sorting
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
++  	{
++  		RandomAccessIter max, min;
++  		find_extremes(first, last, max, min, comp);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
++  		div_type div_min = shift(*min, log_divisor);
++  		div_type div_max = shift(*max, log_divisor);
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		bins[0] = first;
++  		for(unsigned u = 0; u < bin_count - 1; u++)
++  			bins[u + 1] = bins[u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count - 1; ++u)
++  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
++  		bins[bin_count - 1] = last;
++  		
++  		//If we've bucketsorted, the array is sorted and we should skip recursion
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u], comp);
++  			else
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
++  		}
++  	}
++
++  	//Functor implementation for recursive sorting with only Shift overridden
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift)
++  	{
++  		RandomAccessIter max, min;
++  		find_extremes(first, last, max, min);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
++  		div_type div_min = shift(*min, log_divisor);
++  		div_type div_max = shift(*max, log_divisor);
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		bins[0] = first;
++  		for(unsigned u = 0; u < bin_count - 1; u++)
++  			bins[u + 1] = bins[u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned ii = 0; ii < bin_count - 1; ++ii)
++  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
++  		bins[bin_count - 1] = last;
++  		
++  		//If we've bucketsorted, the array is sorted and we should skip recursion
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			else
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
++  		}
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void 
++  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
++  	}
++  }
++
++  //Top-level sorting call for integers
++  template <class RandomAccessIter>
++  inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::spread_sort(first, last, *first >> 0, *first);
++  }
++
++  //integer_sort with functors
++  template <class RandomAccessIter, class right_shift, class compare>
++  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
++  						right_shift shift, compare comp) {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else
++  		detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
++  }
++
++  //integer_sort with right_shift functor
++  template <class RandomAccessIter, class right_shift>
++  inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
++  						right_shift shift) {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::spread_sort(first, last, shift(*first, 0), *first, shift);
++  }
++
++  //------------------------------------------------------ float_sort source --------------------------------------
++  //Casts a RandomAccessIter to the specified data type
++  template<class cast_type, class RandomAccessIter>
++  inline cast_type
++  cast_float_iter(const RandomAccessIter & floatiter)
++  {
++  	cast_type result;
++  	std::memcpy(&result, &(*floatiter), sizeof(cast_type));
++  	return result;
++  }
++
++  //Casts a data element to the specified datinner_float_a type
++  template<class data_type, class cast_type>
++  inline cast_type
++  mem_cast(const data_type & data)
++  {
++  	cast_type result;
++  	std::memcpy(&result, &data, sizeof(cast_type));
++  	return result;
++  }
++
++  namespace detail {
++  	template <class RandomAccessIter, class div_type, class right_shift>
++  	inline void 
++  	find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
++  	{
++  		min = max = shift(*current, 0);
++  		while(++current < last) {
++  			div_type value = shift(*current, 0);
++  			if(max < value)
++  				max = value;
++  			else if(value < min)
++  				min = value;
++  		}
++  	}
++
++  	//Specialized swap loops for floating-point casting
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
++  		, const unsigned log_divisor, const div_type div_min) 
++  	{
++  		RandomAccessIter * local_bin = bins + ii;
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min));  target_bin != local_bin; 
++  				target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
++  				data_type tmp;
++  				RandomAccessIter b = (*target_bin)++;
++  				RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
++  				//Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
++  				if (b_bin != local_bin) {
++  					RandomAccessIter c = (*b_bin)++;
++  					tmp = *c;
++  					*c = *b;
++  				} 
++  				else
++  					tmp = *b;
++  				*b = *current;
++  				*current = tmp;
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
++  		, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 
++  	{
++  		nextbinstart += bin_sizes[ii];
++  		inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
++  	}
++
++  	template <class RandomAccessIter, class cast_type>
++  	inline void 
++  	find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
++  	{
++  		min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
++  		while(++current < last) {
++  			cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
++  			if(max < value)
++  				max = value;
++  			else if(value < min)
++  				min = value;
++  		}
++  	}
++
++  	//Special-case sorting of positive floats with casting instead of a right_shift
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void 
++  	positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
++  		bins[0] = first;
++  		for(unsigned u = 0; u < bin_count - 1; u++)
++  			bins[u + 1] = bins[u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count - 1; ++u)
++  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
++  		bins[bin_count - 1] = last;
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			else
++  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Sorting negative_ float_s
++  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void 
++  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
++  		bins[bin_count - 1] = first;
++  		for(int ii = bin_count - 2; ii >= 0; --ii)
++  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//The last bin will always have the correct elements in it
++  		for(int ii = bin_count - 1; ii > 0; --ii)
++  			float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
++  		//Since we don't process the last bin, we need to update its end position
++  		bin_cache[cache_offset] = last;
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii]);
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Sorting negative_ float_s
++  	//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min, shift);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		bins[bin_count - 1] = first;
++  		for(int ii = bin_count - 2; ii >= 0; --ii)
++  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//The last bin will always have the correct elements in it
++  		for(int ii = bin_count - 1; ii > 0; --ii)
++  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
++  		//Since we don't process the last bin, we need to update its end position
++  		bin_cache[cache_offset] = last;
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii]);
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
++  		}
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min, shift);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		bins[bin_count - 1] = first;
++  		for(int ii = bin_count - 2; ii >= 0; --ii)
++  			bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//The last bin will always have the correct elements in it
++  		for(int ii = bin_count - 1; ii > 0; --ii)
++  			swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
++  		//Since we don't process the last bin, we need to update its end position
++  		bin_cache[cache_offset] = last;
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Recursing
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii], comp);
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
++  		}
++  	}
++
++  	//Casting special-case for floating-point sorting
++  	template <class RandomAccessIter, class div_type, class data_type>
++  	inline void 
++  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
++  		//The index of the first positive bin
++  		div_type first_positive = (div_min < 0) ? -div_min : 0;
++  		//Resetting if all bins are negative
++  		if(cache_offset + first_positive > cache_end)
++  			first_positive = cache_end - cache_offset;
++  		//Reversing the order of the negative bins
++  		//Note that because of the negative/positive ordering direction flip
++  		//We can not depend upon bin order and positions matching up
++  		//so bin_sizes must be reused to contain the end of the bin
++  		if(first_positive > 0) {
++  			bins[first_positive - 1] = first;
++  			for(int ii = first_positive - 2; ii >= 0; --ii) {
++  				bins[ii] = first + bin_sizes[ii + 1];
++  				bin_sizes[ii] += bin_sizes[ii + 1];
++  			}
++  			//Handling positives following negatives
++  			if((unsigned)first_positive < bin_count) {
++  				bins[first_positive] = first + bin_sizes[0];
++  				bin_sizes[first_positive] += bin_sizes[0];
++  			}
++  		}
++  		else
++  			bins[0] = first;
++  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
++  			bins[u + 1] = first + bin_sizes[u];
++  			bin_sizes[u + 1] += bin_sizes[u];
++  		}
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count; ++u) {
++  			nextbinstart = first + bin_sizes[u];
++  			inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
++  		}
++  		
++  		if(!log_divisor)
++  			return;
++  		
++  		//Handling negative values first
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii]);
++  			//sort negative values using reversed-bin spread_sort
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
++  		}
++  		
++  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			//sort positive values using normal spread_sort
++  			else
++  				positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Functor implementation for recursive sorting
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min, shift);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		//The index of the first positive bin
++  		div_type first_positive = (div_min < 0) ? -div_min : 0;
++  		//Resetting if all bins are negative
++  		if(cache_offset + first_positive > cache_end)
++  			first_positive = cache_end - cache_offset;
++  		//Reversing the order of the negative bins
++  		//Note that because of the negative/positive ordering direction flip
++  		//We can not depend upon bin order and positions matching up
++  		//so bin_sizes must be reused to contain the end of the bin
++  		if(first_positive > 0) {
++  			bins[first_positive - 1] = first;
++  			for(int ii = first_positive - 2; ii >= 0; --ii) {
++  				bins[ii] = first + bin_sizes[ii + 1];
++  				bin_sizes[ii] += bin_sizes[ii + 1];
++  			}
++  			//Handling positives following negatives
++  			if((unsigned)first_positive < bin_count) {
++  				bins[first_positive] = first + bin_sizes[0];
++  				bin_sizes[first_positive] += bin_sizes[0];
++  			}
++  		}
++  		else
++  			bins[0] = first;
++  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
++  			bins[u + 1] = first + bin_sizes[u];
++  			bin_sizes[u + 1] += bin_sizes[u];
++  		}
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count; ++u) {
++  			nextbinstart = first + bin_sizes[u];
++  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
++  		}
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Handling negative values first
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii]);
++  			//sort negative values using reversed-bin spread_sort
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
++  		}
++  		
++  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			//sort positive values using normal spread_sort
++  			else
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
++  		}
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
++  					, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
++  	{
++  		div_type max, min;
++  		find_extremes(first, last, max, min, shift);
++  		if(max == min)
++  			return;
++  		unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
++  		div_type div_min = min >> log_divisor;
++  		div_type div_max = max >> log_divisor;
++  		unsigned bin_count = div_max - div_min + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
++  			
++  		//Calculating the size of each bin
++  		for (RandomAccessIter current = first; current != last;)
++  			bin_sizes[shift(*(current++), log_divisor) - div_min]++;
++  		//The index of the first positive bin
++  		div_type first_positive = (div_min < 0) ? -div_min : 0;
++  		//Resetting if all bins are negative
++  		if(cache_offset + first_positive > cache_end)
++  			first_positive = cache_end - cache_offset;
++  		//Reversing the order of the negative bins
++  		//Note that because of the negative/positive ordering direction flip
++  		//We can not depend upon bin order and positions matching up
++  		//so bin_sizes must be reused to contain the end of the bin
++  		if(first_positive > 0) {
++  			bins[first_positive - 1] = first;
++  			for(int ii = first_positive - 2; ii >= 0; --ii) {
++  				bins[ii] = first + bin_sizes[ii + 1];
++  				bin_sizes[ii] += bin_sizes[ii + 1];
++  			}
++  			//Handling positives following negatives
++  			if((unsigned)first_positive < bin_count) {
++  				bins[first_positive] = first + bin_sizes[0];
++  				bin_sizes[first_positive] += bin_sizes[0];
++  			}
++  		}
++  		else
++  			bins[0] = first;
++  		for(unsigned u = first_positive; u < bin_count - 1; u++) {
++  			bins[u + 1] = first + bin_sizes[u];
++  			bin_sizes[u + 1] += bin_sizes[u];
++  		}
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		for(unsigned u = 0; u < bin_count; ++u) {
++  			nextbinstart = first + bin_sizes[u];
++  			inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
++  		}
++  		
++  		//Return if we've completed bucketsorting
++  		if(!log_divisor)
++  			return;
++  		
++  		//Handling negative values first
++  		size_t max_count = get_max_count(log_divisor, last - first);
++  		RandomAccessIter lastPos = first;
++  		for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
++  			size_t count = bin_cache[ii] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[ii]);
++  			//sort negative values using reversed-bin spread_sort
++  			else
++  				negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
++  		}
++  		
++  		for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			if(count < 2)
++  				continue;
++  			if(count < max_count)
++  				std::sort(lastPos, bin_cache[u]);
++  			//sort positive values using normal spread_sort
++  			else
++  				spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
++  		}
++  	}
++
++  	template <class RandomAccessIter, class cast_type, class data_type>
++  	inline void 
++  	float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift>
++  	inline void 
++  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
++  	}
++
++  	template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
++  	inline void 
++  	float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
++  	}
++  }
++
++  //float_sort with casting
++  //The cast_type must be equal in size to the data type, and must be a signed integer
++  template <class RandomAccessIter, class cast_type>
++  inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::float_Sort(first, last, cVal, *first);
++  }
++
++  //float_sort with casting to an int
++  //Only use this with IEEE floating-point numbers
++  template <class RandomAccessIter>
++  inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 
++  {
++  	int cVal = 0;
++  	float_sort_cast(first, last, cVal);
++  }
++
++  //float_sort with functors
++  template <class RandomAccessIter, class right_shift>
++  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::float_Sort(first, last, shift(*first, 0), *first, shift);
++  }
++
++  template <class RandomAccessIter, class right_shift, class compare>
++  inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 
++  {
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else
++  		detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
++  }
++
++  //------------------------------------------------- string_sort source ---------------------------------------------
++  namespace detail {
++  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
++  	template<class RandomAccessIter>
++  	inline void
++  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
++  	{
++  		unsigned nextOffset = char_offset;
++  		bool done = false;
++  		while(!done) {
++  			RandomAccessIter curr = first;
++  			do {
++  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
++  				if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
++  					done = true;
++  					break;
++  				}
++  			} while(++curr != finish);
++  			if(!done)
++  				++nextOffset;
++  		} 
++  		char_offset = nextOffset;
++  	}
++
++  	//Offsetting on identical characters.  This function works a character at a time for optimal worst-case performance.
++  	template<class RandomAccessIter, class get_char, class get_length>
++  	inline void
++  	update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
++  	{
++  		unsigned nextOffset = char_offset;
++  		bool done = false;
++  		while(!done) {
++  			RandomAccessIter curr = first;
++  			do {
++  				//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
++  				if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
++  					done = true;
++  					break;
++  				}
++  			} while(++curr != finish);
++  			if(!done)
++  				++nextOffset;
++  		} 
++  		char_offset = nextOffset;
++  	}
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class unsignedchar_type>
++  	struct offset_lessthan {
++  		offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(x.size(), y.size());
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
++  					return true;
++  				else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
++  					return false;
++  			}
++  			return x.size() < y.size();
++  		}
++  		unsigned fchar_offset;
++  	};
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class unsignedchar_type>
++  	struct offset_greaterthan {
++  		offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(x.size(), y.size());
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
++  					return true;
++  				else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
++  					return false;
++  			}
++  			return x.size() > y.size();
++  		}
++  		unsigned fchar_offset;
++  	};
++
++  	//A comparison functor for strings that assumes they are identical up to char_offset
++  	template<class data_type, class get_char, class get_length>
++  	struct offset_char_lessthan {
++  		offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
++  		inline bool operator()(const data_type &x, const data_type &y) const 
++  		{
++  			unsigned minSize = std::min(length(x), length(y));
++  			for(unsigned u = fchar_offset; u < minSize; ++u) {
++  				if(getchar(x, u) < getchar(y, u))
++  					return true;
++  				else if(getchar(y, u) < getchar(x, u))
++  					return false;
++  			}
++  			return length(x) < length(y);
++  		}
++  		unsigned fchar_offset;
++  		get_char getchar;
++  		get_length length;
++  	};
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while((*first).size() <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;(*finish).size() <= char_offset; --finish) { }
++  		++finish;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(first, finish, char_offset);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if((*current).size() <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while((*current).size() > char_offset) {
++  				target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u + 1];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
++  					target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_size)
++  				std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//Sorts strings in reverse order, with empties at the end
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		RandomAccessIter curr = first;
++  		//Iterate to the end of the empties.  If all empty, return
++  		while((*curr).size() <= char_offset) {
++  			if(++curr == last)
++  				return;
++  		}
++  		//Getting the last non-empty
++  		while((*(--last)).size() <= char_offset) { }
++  		++last;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(curr, last, char_offset);
++  		RandomAccessIter * target_bin;
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		const unsigned max_bin = bin_count - 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
++  		RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if((*current).size() <= char_offset) {
++  				bin_sizes[bin_count]++;
++  			}
++  			else
++  				bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = last;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
++  		RandomAccessIter lastFull = *local_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while((*current).size() > char_offset) {
++  				target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		nextbinstart = first;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = max_bin;
++  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);  target_bin != local_bin; 
++  					target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = lastFull;
++  		//Recursing
++  		RandomAccessIter lastPos = first;
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_size)
++  				std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
++  			else
++  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
++  		}
++  	}
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*first) <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;length(*finish) <= char_offset; --finish) { }
++  		++finish;
++  		update_offset(first, finish, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[getchar((*current), char_offset) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = bins + getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned ii = 0; ii < last_bin; ++ii) {
++  			local_bin = bins + ii;
++  			nextbinstart += bin_sizes[ii + 1];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = bins + getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_size)
++  				std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
++  		}
++  	}
++
++  	//String sorting recursive implementation
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
++  	inline void 
++  	string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*first) <= char_offset) {
++  			if(++first == last)
++  				return;
++  		}
++  		RandomAccessIter finish = last - 1;
++  		//Getting the last non-empty
++  		for(;length(*finish) <= char_offset; --finish) { }
++  		++finish;
++  		update_offset(first, finish, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[0]++;
++  			}
++  			else
++  				bin_sizes[getchar((*current), char_offset) + 1]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = first;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
++  		nextbinstart +=	bin_sizes[0];
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = bins + getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = bin_count - 1;
++  		for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u + 1];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = bins + getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = bins + getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = last;
++  		
++  		//Recursing
++  		RandomAccessIter lastPos = bin_cache[cache_offset];
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_size)
++  				std::sort(lastPos, bin_cache[u], comp);
++  			else
++  				string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
++  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
++  		}
++  	}
++
++  	//Sorts strings in reverse order, with empties at the end
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
++  	inline void 
++  	reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
++  		, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
++  	{
++  		//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
++  		RandomAccessIter curr = first;
++  		//Iterate to the end of the empties.  If all empty, return
++  		while(length(*curr) <= char_offset) {
++  			if(++curr == last)
++  				return;
++  		}
++  		//Getting the last non-empty
++  		while(length(*(--last)) <= char_offset) { }
++  		++last;
++  		//Offsetting on identical characters.  This section works a character at a time for optimal worst-case performance.
++  		update_offset(first, last, char_offset, getchar, length);
++  		
++  		const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
++  		//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
++  		const unsigned max_size = bin_count;
++  		const unsigned membin_count = bin_count + 1;
++  		const unsigned max_bin = bin_count - 1;
++  		unsigned cache_end;
++  		RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
++  		RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
++  			
++  		//Calculating the size of each bin; this takes roughly 10% of runtime
++  		for (RandomAccessIter current = first; current != last; ++current) {
++  			if(length(*current) <= char_offset) {
++  				bin_sizes[bin_count]++;
++  			}
++  			else
++  				bin_sizes[max_bin - getchar((*current), char_offset)]++;
++  		}
++  		//Assign the bin positions
++  		bin_cache[cache_offset] = first;
++  		for(unsigned u = 0; u < membin_count - 1; u++)
++  			bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
++  		
++  		//Swap into place
++  		RandomAccessIter nextbinstart = last;
++  		//handling empty bins
++  		RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
++  		RandomAccessIter lastFull = *local_bin;
++  		RandomAccessIter * target_bin;
++  		//Iterating over each element in the bin of empties
++  		for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  			//empties belong in this bin
++  			while(length(*current) > char_offset) {
++  				target_bin = end_bin - getchar((*current), char_offset);
++  				iter_swap(current, (*target_bin)++);
++  			}
++  		}
++  		*local_bin = nextbinstart;
++  		nextbinstart = first;
++  		//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
++  		unsigned last_bin = max_bin;
++  		for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
++  		//This dominates runtime, mostly in the swap and bin lookups
++  		for(unsigned u = 0; u < last_bin; ++u) {
++  			local_bin = bins + u;
++  			nextbinstart += bin_sizes[u];
++  			//Iterating over each element in this bin
++  			for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
++  				//Swapping elements in current into place until the correct element has been swapped in
++  				for(target_bin = end_bin - getchar((*current), char_offset);  target_bin != local_bin; 
++  					target_bin = end_bin - getchar((*current), char_offset))
++  					iter_swap(current, (*target_bin)++);
++  			}
++  			*local_bin = nextbinstart;
++  		}
++  		bins[last_bin] = lastFull;
++  		//Recursing
++  		RandomAccessIter lastPos = first;
++  		//Skip this loop for empties
++  		for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
++  			size_t count = bin_cache[u] - lastPos;
++  			//don't sort unless there are at least two items to compare
++  			if(count < 2)
++  				continue;
++  			//using std::sort if its worst-case is better
++  			if(count < max_size)
++  				std::sort(lastPos, bin_cache[u], comp);
++  			else
++  				reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
++  					, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
++  		}
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
++  	inline void 
++  	string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
++  	}
++
++  	//Holds the bin vector and makes the initial recursive call
++  	template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
++  	inline void 
++  	reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
++  	{
++  		std::vector<size_t> bin_sizes;
++  		std::vector<RandomAccessIter> bin_cache;
++  		reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
++  	}
++  }
++
++  //Allows character-type overloads
++  template <class RandomAccessIter, class unsignedchar_type>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else
++  		detail::string_sort(first, last, *first, unused);
++  }
++
++  //Top-level sorting call; wraps using default of unsigned char
++  template <class RandomAccessIter>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last) 
++  {
++  	unsigned char unused = '\0';
++  	string_sort(first, last, unused);
++  }
++
++  //Allows character-type overloads
++  template <class RandomAccessIter, class compare, class unsignedchar_type>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else
++  		detail::reverse_string_sort(first, last, *first, unused);
++  }
++
++  //Top-level sorting call; wraps using default of unsigned char
++  template <class RandomAccessIter, class compare>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 
++  {
++  	unsigned char unused = '\0';
++  	reverse_string_sort(first, last, comp, unused);
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*first)) {
++  			if(++first == last)
++  				return;
++  		}
++  		detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
++  	}
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length, class compare>
++  inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*first)) {
++  			if(++first == last)
++  				return;
++  		}
++  		detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
++  	}
++  }
++
++  template <class RandomAccessIter, class get_char, class get_length, class compare>
++  inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 
++  {
++  	//Don't sort if it's too small to optimize
++  	if(last - first < detail::MIN_SORT_SIZE)
++  		std::sort(first, last, comp);
++  	else {
++  		//skipping past empties at the beginning, which allows us to get the character type 
++  		//.empty() is not used so as not to require a user declaration of it
++  		while(!length(*(--last))) {
++  			//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
++  			if(first == last)
++  				return;
++  		}
++  		//making last just after the end of the non-empty part of the array
++  		++last;
++  		detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
++  	}
++  }
++}
++
++#endif
diff --git a/package/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc b/package/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc
new file mode 100644
index 000000000..beeba8148
--- /dev/null
+++ b/package/gcc/patches/4.7.3/patch-libgcc_unwind-arm-common_inc
@@ -0,0 +1,14 @@
+--- gcc-4.7.3.orig/libgcc/unwind-arm-common.inc	2011-12-20 21:54:25.000000000 +0100
++++ gcc-4.7.3/libgcc/unwind-arm-common.inc	2014-02-05 15:10:25.000000000 +0100
+@@ -25,11 +25,6 @@
+ #include "tsystem.h"
+ #include "unwind.h"
+ 
+-/* Used for SystemTap unwinder probe.  */
+-#ifdef HAVE_SYS_SDT_H
+-#include <sys/sdt.h>
+-#endif
+-
+ /* We add a prototype for abort here to avoid creating a dependency on
+    target headers.  */
+ extern void abort (void);
diff --git a/package/gpsd/Makefile b/package/gpsd/Makefile
index 3bed165ab..a161d860f 100644
--- a/package/gpsd/Makefile
+++ b/package/gpsd/Makefile
@@ -4,9 +4,9 @@
 include ${TOPDIR}/rules.mk
 
 PKG_NAME:=		gpsd
-PKG_VERSION:=		3.9
+PKG_VERSION:=		3.10
 PKG_RELEASE:=		1
-PKG_MD5SUM:=		53a88f24a0973d23427e82e9a8914f19
+PKG_MD5SUM:=		fc5b03aae38b9b5b6880b31924d0ace3
 PKG_DESCR:=		An interface daemon for GPS receivers
 PKG_SECTION:=		misc
 PKG_DEPENDS:=		libpthread
@@ -27,8 +27,8 @@ BUILD_STYLE:=		manual
 INSTALL_STYLE:=		manual
 
 do-install:
-	(cd $(WRKBUILD); PATH='$(TARGET_PATH)' CCFLAGS='' \
-		scons install prefix=$(WRKINST)/usr python=no chrpath=no bluez=no usb=no libgpsmm=no)
+	(cd $(WRKBUILD); env PATH='$(TARGET_PATH)' CCFLAGS='' \
+		scons install prefix=$(WRKINST)/usr platform=linux python=no chrpath=no bluez=no usb=no libgpsmm=no)
 
 gpsd-install:
 	${INSTALL_DIR} ${IDIR_GPSD}/usr/lib ${IDIR_GPSD}/usr/sbin
diff --git a/package/gpsd/patches/patch-SConstruct b/package/gpsd/patches/patch-SConstruct
new file mode 100644
index 000000000..0937d9f67
--- /dev/null
+++ b/package/gpsd/patches/patch-SConstruct
@@ -0,0 +1,12 @@
+--- gpsd-3.10.orig/SConstruct	2013-11-22 14:10:01.000000000 +0100
++++ gpsd-3.10/SConstruct	2014-02-07 19:33:32.000000000 +0100
+@@ -231,6 +231,9 @@ for (name, default, help) in pathopts:
+ 
+ env['VERSION'] = gpsd_version
+ env['PYTHON'] = sys.executable
++env['PLATFORM'] = "posix"
++env['SHLIBSUFFIX'] = ".so"
++env['SHLINKFLAGS'] = "-shared"
+ 
+ # Set defaults from environment.  Note that scons doesn't cope well
+ # with multi-word CPPFLAGS/LDFLAGS/SHLINKFLAGS values; you'll have to
diff --git a/package/python2/patches/patch-setup_py b/package/python2/patches/patch-setup_py
index 3a80230c2..4973a91b2 100644
--- a/package/python2/patches/patch-setup_py
+++ b/package/python2/patches/patch-setup_py
@@ -1,5 +1,5 @@
 --- Python-2.7.5.orig/setup.py	2013-05-12 05:32:54.000000000 +0200
-+++ Python-2.7.5/setup.py	2013-11-01 14:53:38.000000000 +0100
++++ Python-2.7.5/setup.py	2014-02-03 17:07:52.000000000 +0100
 @@ -74,7 +74,7 @@ def find_file(filename, std_dirs, paths)
      'paths' is a list of additional locations to check; if the file is
          found in one of them, the resulting list will contain the directory.
@@ -119,12 +119,3 @@
              # This should work on any unixy platform ;-)
              # If the user has bothered specifying additional -I and -L flags
              # in OPT and LDFLAGS we might as well use them here.
-@@ -837,7 +847,7 @@ class PyBuildExt(build_ext):
-                                openssl_ver >= min_openssl_ver)
- 
-         if have_any_openssl:
--            if have_usable_openssl:
-+            if have_usable_openssl and host_platform != 'darwin':
-                 # The _hashlib module wraps optimized implementations
-                 # of hash functions from the OpenSSL library.
-                 exts.append( Extension('_hashlib', ['_hashopenssl.c'],
diff --git a/scripts/config.guess b/scripts/config.guess
index 202f698b2..92fe65f50 100755
--- a/scripts/config.guess
+++ b/scripts/config.guess
@@ -1,14 +1,12 @@
 #! /bin/sh
 # Attempt to guess a canonical system name.
-#   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
-#   2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
-#   Free Software Foundation, Inc.
+#   Copyright 1992-2014 Free Software Foundation, Inc.
 
-timestamp='2008-09-28'
+timestamp='2014-01-25'
 
 # This file is free software; you can redistribute it and/or modify it
 # under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
+# the Free Software Foundation; either version 3 of the License, or
 # (at your option) any later version.
 #
 # This program is distributed in the hope that it will be useful, but
@@ -17,26 +15,22 @@ timestamp='2008-09-28'
 # General Public License for more details.
 #
 # You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
-# 02110-1301, USA.
+# along with this program; if not, see <http://www.gnu.org/licenses/>.
 #
 # As a special exception to the GNU General Public License, if you
 # distribute this file as part of a program that contains a
 # configuration script generated by Autoconf, you may include it under
-# the same distribution terms that you use for the rest of that program.
-
-
-# Originally written by Per Bothner <per@bothner.com>.
-# Please send patches to <config-patches@gnu.org>.  Submit a context
-# diff and a properly formatted ChangeLog entry.
+# the same distribution terms that you use for the rest of that
+# program.  This Exception is an additional permission under section 7
+# of the GNU General Public License, version 3 ("GPLv3").
 #
-# This script attempts to guess a canonical system name similar to
-# config.sub.  If it succeeds, it prints the system name on stdout, and
-# exits with 0.  Otherwise, it exits with 1.
+# Originally written by Per Bothner.
 #
-# The plan is that this can be called by configure scripts if you
-# don't specify an explicit build system type.
+# You can get the latest version of this script from:
+# http://git.savannah.gnu.org/gitweb/?p=config.git;a=blob_plain;f=config.guess;hb=HEAD
+#
+# Please send patches with a ChangeLog entry to config-patches@gnu.org.
+
 
 me=`echo "$0" | sed -e 's,.*/,,'`
 
@@ -56,8 +50,7 @@ version="\
 GNU config.guess ($timestamp)
 
 Originally written by Per Bothner.
-Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
-2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+Copyright 1992-2014 Free Software Foundation, Inc.
 
 This is free software; see the source for copying conditions.  There is NO
 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE."
@@ -139,29 +132,33 @@ UNAME_RELEASE=`(uname -r) 2>/dev/null` || UNAME_RELEASE=unknown
 UNAME_SYSTEM=`(uname -s) 2>/dev/null`  || UNAME_SYSTEM=unknown
 UNAME_VERSION=`(uname -v) 2>/dev/null` || UNAME_VERSION=unknown
 
-if [ "${UNAME_SYSTEM}" = "Linux" ] ; then
+case "${UNAME_SYSTEM}" in
+Linux|GNU|GNU/*)
+	# If the system lacks a compiler, then just pick glibc.
+	# We could probably try harder.
+	LIBC=gnu
+
 	eval $set_cc_for_build
-	cat << EOF > $dummy.c
+	cat <<-EOF > $dummy.c
 	#include <features.h>
-	#ifdef __UCLIBC__
-	# ifdef __UCLIBC_CONFIG_VERSION__
-	LIBC=uclibc __UCLIBC_CONFIG_VERSION__
-	# else
+	#if defined(__UCLIBC__)
 	LIBC=uclibc
-	# endif
+	#elif defined(__dietlibc__)
+	LIBC=dietlibc
 	#else
 	LIBC=gnu
 	#endif
-EOF
-	eval `$CC_FOR_BUILD -E $dummy.c 2>/dev/null | grep LIBC= | sed -e 's: ::g'`
-fi
+	EOF
+	eval `$CC_FOR_BUILD -E $dummy.c 2>/dev/null | grep '^LIBC'`
+	;;
+esac
 
 # Note: order is significant - the case branches are not exclusive.
 
 case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
     *:NetBSD:*:*)
 	# NetBSD (nbsd) targets should (where applicable) match one or
-	# more of the tupples: *-*-netbsdelf*, *-*-netbsdaout*,
+	# more of the tuples: *-*-netbsdelf*, *-*-netbsdaout*,
 	# *-*-netbsdecoff* and *-*-netbsd*.  For targets that recently
 	# switched to ELF, *-*-netbsd* would select the old
 	# object file format.  This provides both forward
@@ -187,7 +184,7 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 	    arm*|i386|m68k|ns32k|sh3*|sparc|vax)
 		eval $set_cc_for_build
 		if echo __ELF__ | $CC_FOR_BUILD -E - 2>/dev/null \
-			| grep __ELF__ >/dev/null
+			| grep -q __ELF__
 		then
 		    # Once all utilities can be ECOFF (netbsdecoff) or a.out (netbsdaout).
 		    # Return netbsd for either.  FIX?
@@ -197,7 +194,7 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 		fi
 		;;
 	    *)
-	        os=netbsd
+		os=netbsd
 		;;
 	esac
 	# The OS release
@@ -218,6 +215,10 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 	# CPU_TYPE-MANUFACTURER-OPERATING_SYSTEM is used.
 	echo "${machine}-${os}${release}"
 	exit ;;
+    *:Bitrig:*:*)
+	UNAME_MACHINE_ARCH=`arch | sed 's/Bitrig.//'`
+	echo ${UNAME_MACHINE_ARCH}-unknown-bitrig${UNAME_RELEASE}
+	exit ;;
     *:OpenBSD:*:*)
 	UNAME_MACHINE_ARCH=`arch | sed 's/OpenBSD.//'`
 	echo ${UNAME_MACHINE_ARCH}-unknown-openbsd${UNAME_RELEASE}
@@ -240,7 +241,7 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 		UNAME_RELEASE=`/usr/sbin/sizer -v | awk '{print $3}'`
 		;;
 	*5.*)
-	        UNAME_RELEASE=`/usr/sbin/sizer -v | awk '{print $4}'`
+		UNAME_RELEASE=`/usr/sbin/sizer -v | awk '{print $4}'`
 		;;
 	esac
 	# According to Compaq, /usr/sbin/psrinfo has been available on
@@ -286,7 +287,10 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 	# A Xn.n version is an unreleased experimental baselevel.
 	# 1.2 uses "1.2" for uname -r.
 	echo ${UNAME_MACHINE}-dec-osf`echo ${UNAME_RELEASE} | sed -e 's/^[PVTX]//' | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz'`
-	exit ;;
+	# Reset EXIT trap before exiting to avoid spurious non-zero exit code.
+	exitcode=$?
+	trap '' 0
+	exit $exitcode ;;
     Alpha\ *:Windows_NT*:*)
 	# How do we know it's Interix rather than the generic POSIX subsystem?
 	# Should we change UNAME_MACHINE based on the output of uname instead
@@ -312,12 +316,12 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 	echo s390-ibm-zvmoe
 	exit ;;
     *:OS400:*:*)
-        echo powerpc-ibm-os400
+	echo powerpc-ibm-os400
 	exit ;;
     arm:RISC*:1.[012]*:*|arm:riscix:1.[012]*:*)
 	echo arm-acorn-riscix${UNAME_RELEASE}
 	exit ;;
-    arm:riscos:*:*|arm:RISCOS:*:*)
+    arm*:riscos:*:*|arm*:RISCOS:*:*)
 	echo arm-unknown-riscos
 	exit ;;
     SR2?01:HI-UX/MPP:*:* | SR8000:HI-UX/MPP:*:*)
@@ -341,14 +345,33 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
 	case `/usr/bin/uname -p` in
 	    sparc) echo sparc-icl-nx7; exit ;;
 	esac ;;
+    s390x:SunOS:*:*)
+	echo ${UNAME_MACHINE}-ibm-solaris2`echo ${UNAME_RELEASE}|sed -e 's/[^.]*//'`
+	exit ;;
     sun4H:SunOS:5.*:*)
 	echo sparc-hal-solaris2`echo ${UNAME_RELEASE}|sed -e 's/[^.]*//'`
 	exit ;;
     sun4*:SunOS:5.*:* | tadpole*:SunOS:5.*:*)
 	echo sparc-sun-solaris2`echo ${UNAME_RELEASE}|sed -e 's/[^.]*//'`
 	exit ;;
+    i86pc:AuroraUX:5.*:* | i86xen:AuroraUX:5.*:*)
+	echo i386-pc-auroraux${UNAME_RELEASE}
+	exit ;;
     i86pc:SunOS:5.*:* | i86xen:SunOS:5.*:*)
-	echo i386-pc-solaris2`echo ${UNAME_RELEASE}|sed -e 's/[^.]*//'`
+	eval $set_cc_for_build
+	SUN_ARCH="i386"
+	# If there is a compiler, see if it is configured for 64-bit objects.
+	# Note that the Sun cc does not turn __LP64__ into 1 like gcc does.
+	# This test works for both compilers.
+	if [ "$CC_FOR_BUILD" != 'no_compiler_found' ]; then
+	    if (echo '#ifdef __amd64'; echo IS_64BIT_ARCH; echo '#endif') | \
+		(CCOPTS= $CC_FOR_BUILD -E - 2>/dev/null) | \
+		grep IS_64BIT_ARCH >/dev/null
+	    then
+		SUN_ARCH="x86_64"
+	    fi
+	fi
+	echo ${SUN_ARCH}-pc-solaris2`echo ${UNAME_RELEASE}|sed -e 's/[^.]*//'`
 	exit ;;
     sun4*:SunOS:6*:*)
 	# According to config.sub, this is the proper way to canonicalize
@@ -392,23 +415,23 @@ case "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" in
     # MiNT.  But MiNT is downward compatible to TOS, so this should
     # be no problem.
     atarist[e]:*MiNT:*:* | atarist[e]:*mint:*:* | atarist[e]:*TOS:*:*)
-        echo m68k-atari-mint${UNAME_RELEASE}
+	echo m68k-atari-mint${UNAME_RELEASE}
 	exit ;;
     atari*:*MiNT:*:* | atari*:*mint:*:* | atarist[e]:*TOS:*:*)
 	echo m68k-atari-mint${UNAME_RELEASE}
-        exit ;;
+	exit ;;
     *falcon*:*MiNT:*:* | *falcon*:*mint:*:* | *falcon*:*TOS:*:*)
-        echo m68k-atari-mint${UNAME_RELEASE}
+	echo m68k-atari-mint${UNAME_RELEASE}
 	exit ;;
     milan*:*MiNT:*:* | milan*:*mint:*:* | *milan*:*TOS:*:*)
-        echo m68k-milan-mint${UNAME_RELEASE}
-        exit ;;
+	echo m68k-milan-mint${UNAME_RELEASE}
+	exit ;;
     hades*:*MiNT:*:* | hades*:*mint:*:* | *hades*:*TOS:*:*)
-        echo m68k-hades-mint${UNAME_RELEASE}
-        exit ;;
+	echo m68k-hades-mint${UNAME_RELEASE}
+	exit ;;
     *:*MiNT:*:* | *:*mint:*:* | *:*TOS:*:*)
-        echo m68k-unknown-mint${UNAME_RELEASE}
-        exit ;;
+	echo m68k-unknown-mint${UNAME_RELEASE}
+	exit ;;
     m68k:machten:*:*)
 	echo m68k-apple-machten${UNAME_RELEASE}
 	exit ;;
@@ -478,8 +501,8 @@ EOF
 	echo m88k-motorola-sysv3
 	exit ;;
     AViiON:dgux:*:*)
-        # DG/UX returns AViiON for all architectures
-        UNAME_PROCESSOR=`/usr/bin/uname -p`
+	# DG/UX returns AViiON for all architectures
+	UNAME_PROCESSOR=`/usr/bin/uname -p`
 	if [ $UNAME_PROCESSOR = mc88100 ] || [ $UNAME_PROCESSOR = mc88110 ]
 	then
 	    if [ ${TARGET_BINARY_INTERFACE}x = m88kdguxelfx ] || \
@@ -492,7 +515,7 @@ EOF
 	else
 	    echo i586-dg-dgux${UNAME_RELEASE}
 	fi
- 	exit ;;
+	exit ;;
     M88*:DolphinOS:*:*)	# DolphinOS (SVR3)
 	echo m88k-dolphin-sysv3
 	exit ;;
@@ -549,7 +572,7 @@ EOF
 		echo rs6000-ibm-aix3.2
 	fi
 	exit ;;
-    *:AIX:*:[456])
+    *:AIX:*:[4567])
 	IBM_CPU_ID=`/usr/sbin/lsdev -C -c processor -S available | sed 1q | awk '{ print $1 }'`
 	if /usr/sbin/lsattr -El ${IBM_CPU_ID} | grep ' POWER' >/dev/null 2>&1; then
 		IBM_ARCH=rs6000
@@ -592,52 +615,52 @@ EOF
 	    9000/[678][0-9][0-9])
 		if [ -x /usr/bin/getconf ]; then
 		    sc_cpu_version=`/usr/bin/getconf SC_CPU_VERSION 2>/dev/null`
-                    sc_kernel_bits=`/usr/bin/getconf SC_KERNEL_BITS 2>/dev/null`
-                    case "${sc_cpu_version}" in
-                      523) HP_ARCH="hppa1.0" ;; # CPU_PA_RISC1_0
-                      528) HP_ARCH="hppa1.1" ;; # CPU_PA_RISC1_1
-                      532)                      # CPU_PA_RISC2_0
-                        case "${sc_kernel_bits}" in
-                          32) HP_ARCH="hppa2.0n" ;;
-                          64) HP_ARCH="hppa2.0w" ;;
+		    sc_kernel_bits=`/usr/bin/getconf SC_KERNEL_BITS 2>/dev/null`
+		    case "${sc_cpu_version}" in
+		      523) HP_ARCH="hppa1.0" ;; # CPU_PA_RISC1_0
+		      528) HP_ARCH="hppa1.1" ;; # CPU_PA_RISC1_1
+		      532)                      # CPU_PA_RISC2_0
+			case "${sc_kernel_bits}" in
+			  32) HP_ARCH="hppa2.0n" ;;
+			  64) HP_ARCH="hppa2.0w" ;;
 			  '') HP_ARCH="hppa2.0" ;;   # HP-UX 10.20
-                        esac ;;
-                    esac
+			esac ;;
+		    esac
 		fi
 		if [ "${HP_ARCH}" = "" ]; then
 		    eval $set_cc_for_build
-		    sed 's/^              //' << EOF >$dummy.c
+		    sed 's/^		//' << EOF >$dummy.c
 
-              #define _HPUX_SOURCE
-              #include <stdlib.h>
-              #include <unistd.h>
+		#define _HPUX_SOURCE
+		#include <stdlib.h>
+		#include <unistd.h>
 
-              int main ()
-              {
-              #if defined(_SC_KERNEL_BITS)
-                  long bits = sysconf(_SC_KERNEL_BITS);
-              #endif
-                  long cpu  = sysconf (_SC_CPU_VERSION);
+		int main ()
+		{
+		#if defined(_SC_KERNEL_BITS)
+		    long bits = sysconf(_SC_KERNEL_BITS);
+		#endif
+		    long cpu  = sysconf (_SC_CPU_VERSION);
 
-                  switch (cpu)
-              	{
-              	case CPU_PA_RISC1_0: puts ("hppa1.0"); break;
-              	case CPU_PA_RISC1_1: puts ("hppa1.1"); break;
-              	case CPU_PA_RISC2_0:
-              #if defined(_SC_KERNEL_BITS)
-              	    switch (bits)
-              		{
-              		case 64: puts ("hppa2.0w"); break;
-              		case 32: puts ("hppa2.0n"); break;
-              		default: puts ("hppa2.0"); break;
-              		} break;
-              #else  /* !defined(_SC_KERNEL_BITS) */
-              	    puts ("hppa2.0"); break;
-              #endif
-              	default: puts ("hppa1.0"); break;
-              	}
-                  exit (0);
-              }
+		    switch (cpu)
+			{
+			case CPU_PA_RISC1_0: puts ("hppa1.0"); break;
+			case CPU_PA_RISC1_1: puts ("hppa1.1"); break;
+			case CPU_PA_RISC2_0:
+		#if defined(_SC_KERNEL_BITS)
+			    switch (bits)
+				{
+				case 64: puts ("hppa2.0w"); break;
+				case 32: puts ("hppa2.0n"); break;
+				default: puts ("hppa2.0"); break;
+				} break;
+		#else  /* !defined(_SC_KERNEL_BITS) */
+			    puts ("hppa2.0"); break;
+		#endif
+			default: puts ("hppa1.0"); break;
+			}
+		    exit (0);
+		}
 EOF
 		    (CCOPTS= $CC_FOR_BUILD -o $dummy $dummy.c 2>/dev/null) && HP_ARCH=`$dummy`
 		    test -z "$HP_ARCH" && HP_ARCH=hppa
@@ -657,7 +680,7 @@ EOF
 	    # => hppa64-hp-hpux11.23
 
 	    if echo __LP64__ | (CCOPTS= $CC_FOR_BUILD -E - 2>/dev/null) |
-		grep __LP64__ >/dev/null
+		grep -q __LP64__
 	    then
 		HP_ARCH="hppa2.0w"
 	    else
@@ -728,22 +751,22 @@ EOF
 	exit ;;
     C1*:ConvexOS:*:* | convex:ConvexOS:C1*:*)
 	echo c1-convex-bsd
-        exit ;;
+	exit ;;
     C2*:ConvexOS:*:* | convex:ConvexOS:C2*:*)
 	if getsysinfo -f scalar_acc
 	then echo c32-convex-bsd
 	else echo c2-convex-bsd
 	fi
-        exit ;;
+	exit ;;
     C34*:ConvexOS:*:* | convex:ConvexOS:C34*:*)
 	echo c34-convex-bsd
-        exit ;;
+	exit ;;
     C38*:ConvexOS:*:* | convex:ConvexOS:C38*:*)
 	echo c38-convex-bsd
-        exit ;;
+	exit ;;
     C4*:ConvexOS:*:* | convex:ConvexOS:C4*:*)
 	echo c4-convex-bsd
-        exit ;;
+	exit ;;
     CRAY*Y-MP:*:*:*)
 	echo ymp-cray-unicos${UNAME_RELEASE} | sed -e 's/\.[^.]*$/.X/'
 	exit ;;
@@ -767,14 +790,14 @@ EOF
 	exit ;;
     F30[01]:UNIX_System_V:*:* | F700:UNIX_System_V:*:*)
 	FUJITSU_PROC=`uname -m | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz'`
-        FUJITSU_SYS=`uname -p | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/\///'`
-        FUJITSU_REL=`echo ${UNAME_RELEASE} | sed -e 's/ /_/'`
-        echo "${FUJITSU_PROC}-fujitsu-${FUJITSU_SYS}${FUJITSU_REL}"
-        exit ;;
+	FUJITSU_SYS=`uname -p | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/\///'`
+	FUJITSU_REL=`echo ${UNAME_RELEASE} | sed -e 's/ /_/'`
+	echo "${FUJITSU_PROC}-fujitsu-${FUJITSU_SYS}${FUJITSU_REL}"
+	exit ;;
     5000:UNIX_System_V:4.*:*)
-        FUJITSU_SYS=`uname -p | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/\///'`
-        FUJITSU_REL=`echo ${UNAME_RELEASE} | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/ /_/'`
-        echo "sparc-fujitsu-${FUJITSU_SYS}${FUJITSU_REL}"
+	FUJITSU_SYS=`uname -p | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/\///'`
+	FUJITSU_REL=`echo ${UNAME_RELEASE} | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'abcdefghijklmnopqrstuvwxyz' | sed -e 's/ /_/'`
+	echo "sparc-fujitsu-${FUJITSU_SYS}${FUJITSU_REL}"
 	exit ;;
     i*86:BSD/386:*:* | i*86:BSD/OS:*:* | *:Ascend\ Embedded/OS:*:*)
 	echo ${UNAME_MACHINE}-pc-bsdi${UNAME_RELEASE}
@@ -786,34 +809,39 @@ EOF
 	echo ${UNAME_MACHINE}-unknown-bsdi${UNAME_RELEASE}
 	exit ;;
     *:FreeBSD:*:*)
-	case ${UNAME_MACHINE} in
-	    pc98)
-		echo i386-unknown-freebsd`echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'` ;;
+	UNAME_PROCESSOR=`/usr/bin/uname -p`
+	case ${UNAME_PROCESSOR} in
 	    amd64)
 		echo x86_64-unknown-freebsd`echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'` ;;
 	    *)
-		echo ${UNAME_MACHINE}-unknown-freebsd`echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'` ;;
+		echo ${UNAME_PROCESSOR}-unknown-freebsd`echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'` ;;
 	esac
 	exit ;;
     i*:CYGWIN*:*)
 	echo ${UNAME_MACHINE}-pc-cygwin
 	exit ;;
+    *:MINGW64*:*)
+	echo ${UNAME_MACHINE}-pc-mingw64
+	exit ;;
     *:MINGW*:*)
 	echo ${UNAME_MACHINE}-pc-mingw32
 	exit ;;
+    i*:MSYS*:*)
+	echo ${UNAME_MACHINE}-pc-msys
+	exit ;;
     i*:windows32*:*)
-    	# uname -m includes "-pc" on this system.
-    	echo ${UNAME_MACHINE}-mingw32
+	# uname -m includes "-pc" on this system.
+	echo ${UNAME_MACHINE}-mingw32
 	exit ;;
     i*:PW*:*)
 	echo ${UNAME_MACHINE}-pc-pw32
 	exit ;;
-    *:Interix*:[3456]*)
-    	case ${UNAME_MACHINE} in
+    *:Interix*:*)
+	case ${UNAME_MACHINE} in
 	    x86)
 		echo i586-pc-interix${UNAME_RELEASE}
 		exit ;;
-	    EM64T | authenticamd | genuineintel)
+	    authenticamd | genuineintel | EM64T)
 		echo x86_64-unknown-interix${UNAME_RELEASE}
 		exit ;;
 	    IA64)
@@ -823,6 +851,9 @@ EOF
     [345]86:Windows_95:* | [345]86:Windows_98:* | [345]86:Windows_NT:*)
 	echo i${UNAME_MACHINE}-pc-mks
 	exit ;;
+    8664:Windows_NT:*)
+	echo x86_64-pc-mks
+	exit ;;
     i*:Windows_NT*:* | Pentium*:Windows_NT*:*)
 	# How do we know it's Interix rather than the generic POSIX subsystem?
 	# It also conflicts with pre-2.0 versions of AT&T UWIN. Should we
@@ -843,15 +874,39 @@ EOF
 	exit ;;
     *:GNU:*:*)
 	# the GNU system
-	echo `echo ${UNAME_MACHINE}|sed -e 's,[-/].*$,,'`-unknown-gnu`echo ${UNAME_RELEASE}|sed -e 's,/.*$,,'`
+	echo `echo ${UNAME_MACHINE}|sed -e 's,[-/].*$,,'`-unknown-${LIBC}`echo ${UNAME_RELEASE}|sed -e 's,/.*$,,'`
 	exit ;;
     *:GNU/*:*:*)
 	# other systems with GNU libc and userland
-	echo ${UNAME_MACHINE}-unknown-`echo ${UNAME_SYSTEM} | sed 's,^[^/]*/,,' | tr '[A-Z]' '[a-z]'``echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'`-gnu
+	echo ${UNAME_MACHINE}-unknown-`echo ${UNAME_SYSTEM} | sed 's,^[^/]*/,,' | tr '[A-Z]' '[a-z]'``echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'`-${LIBC}
 	exit ;;
     i*86:Minix:*:*)
 	echo ${UNAME_MACHINE}-pc-minix
 	exit ;;
+    aarch64:Linux:*:*)
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
+    aarch64_be:Linux:*:*)
+	UNAME_MACHINE=aarch64_be
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
+    alpha:Linux:*:*)
+	case `sed -n '/^cpu model/s/^.*: \(.*\)/\1/p' < /proc/cpuinfo` in
+	  EV5)   UNAME_MACHINE=alphaev5 ;;
+	  EV56)  UNAME_MACHINE=alphaev56 ;;
+	  PCA56) UNAME_MACHINE=alphapca56 ;;
+	  PCA57) UNAME_MACHINE=alphapca56 ;;
+	  EV6)   UNAME_MACHINE=alphaev6 ;;
+	  EV67)  UNAME_MACHINE=alphaev67 ;;
+	  EV68*) UNAME_MACHINE=alphaev68 ;;
+	esac
+	objdump --private-headers /bin/sh | grep -q ld.so.1
+	if test "$?" = 0 ; then LIBC="gnulibc1" ; fi
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
+    arc:Linux:*:* | arceb:Linux:*:*)
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
     arm*:Linux:*:*)
 	eval $set_cc_for_build
 	if echo __ARM_EABI__ | $CC_FOR_BUILD -E - 2>/dev/null \
@@ -859,20 +914,32 @@ EOF
 	then
 	    echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	else
-	    echo ${UNAME_MACHINE}-unknown-linux-${LIBC}eabi
+	    if echo __ARM_PCS_VFP | $CC_FOR_BUILD -E - 2>/dev/null \
+		| grep -q __ARM_PCS_VFP
+	    then
+		echo ${UNAME_MACHINE}-unknown-linux-${LIBC}eabi
+	    else
+		echo ${UNAME_MACHINE}-unknown-linux-${LIBC}eabihf
+	    fi
 	fi
 	exit ;;
     avr32*:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
     cris:Linux:*:*)
-	echo cris-axis-linux-${LIBC}
+	echo ${UNAME_MACHINE}-axis-linux-${LIBC}
 	exit ;;
     crisv32:Linux:*:*)
-	echo crisv32-axis-linux-${LIBC}
+	echo ${UNAME_MACHINE}-axis-linux-${LIBC}
 	exit ;;
     frv:Linux:*:*)
-    	echo frv-unknown-linux-${LIBC}
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
+    hexagon:Linux:*:*)
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
+    i*86:Linux:*:*)
+	echo ${UNAME_MACHINE}-pc-linux-${LIBC}
 	exit ;;
     ia64:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
@@ -883,77 +950,36 @@ EOF
     m68*:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
-    mips:Linux:*:*)
-	eval $set_cc_for_build
-	sed 's/^	//' << EOF >$dummy.c
-	#undef CPU
-	#undef mips
-	#undef mipsel
-	#if defined(__MIPSEL__) || defined(__MIPSEL) || defined(_MIPSEL) || defined(MIPSEL)
-	CPU=mipsel
-	#else
-	#if defined(__MIPSEB__) || defined(__MIPSEB) || defined(_MIPSEB) || defined(MIPSEB)
-	CPU=mips
-	#else
-	CPU=
-	#endif
-	#endif
-EOF
-	eval "`$CC_FOR_BUILD -E $dummy.c 2>/dev/null | sed -n '
-	    /^CPU/{
-		s: ::g
-		p
-	    }'`"
-	test x"${CPU}" != x && { echo "${CPU}-unknown-linux-${LIBC}"; exit; }
-	;;
-    mips64:Linux:*:*)
+    mips:Linux:*:* | mips64:Linux:*:*)
 	eval $set_cc_for_build
 	sed 's/^	//' << EOF >$dummy.c
 	#undef CPU
-	#undef mips64
-	#undef mips64el
+	#undef ${UNAME_MACHINE}
+	#undef ${UNAME_MACHINE}el
 	#if defined(__MIPSEL__) || defined(__MIPSEL) || defined(_MIPSEL) || defined(MIPSEL)
-	CPU=mips64el
+	CPU=${UNAME_MACHINE}el
 	#else
 	#if defined(__MIPSEB__) || defined(__MIPSEB) || defined(_MIPSEB) || defined(MIPSEB)
-	CPU=mips64
+	CPU=${UNAME_MACHINE}
 	#else
 	CPU=
 	#endif
 	#endif
 EOF
-	eval "`$CC_FOR_BUILD -E $dummy.c 2>/dev/null | sed -n '
-	    /^CPU/{
-		s: ::g
-		p
-	    }'`"
+	eval `$CC_FOR_BUILD -E $dummy.c 2>/dev/null | grep '^CPU'`
 	test x"${CPU}" != x && { echo "${CPU}-unknown-linux-${LIBC}"; exit; }
 	;;
-    or32:Linux:*:*)
-	echo or32-unknown-linux-${LIBC}
-	exit ;;
-    ppc:Linux:*:*)
-	echo powerpc-unknown-linux-${LIBC}
-	exit ;;
-    ppc64:Linux:*:*)
-	echo powerpc64-unknown-linux-${LIBC}
+    or1k:Linux:*:*)
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
-    alpha:Linux:*:*)
-	case `sed -n '/^cpu model/s/^.*: \(.*\)/\1/p' < /proc/cpuinfo` in
-	  EV5)   UNAME_MACHINE=alphaev5 ;;
-	  EV56)  UNAME_MACHINE=alphaev56 ;;
-	  PCA56) UNAME_MACHINE=alphapca56 ;;
-	  PCA57) UNAME_MACHINE=alphapca56 ;;
-	  EV6)   UNAME_MACHINE=alphaev6 ;;
-	  EV67)  UNAME_MACHINE=alphaev67 ;;
-	  EV68*) UNAME_MACHINE=alphaev68 ;;
-        esac
-	objdump --private-headers /bin/sh | grep ld.so.1 >/dev/null
-	if test "$?" = 0 ; then LIBC="gnulibc1" ; fi
+    or32:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
     padre:Linux:*:*)
-	echo sparc-unknown-linux-gnu
+	echo sparc-unknown-linux-${LIBC}
+	exit ;;
+    parisc64:Linux:*:* | hppa64:Linux:*:*)
+	echo hppa64-unknown-linux-${LIBC}
 	exit ;;
     parisc:Linux:*:* | hppa:Linux:*:*)
 	# Look for CPU level
@@ -963,14 +989,23 @@ EOF
 	  *)    echo hppa-unknown-linux-${LIBC} ;;
 	esac
 	exit ;;
-    parisc64:Linux:*:* | hppa64:Linux:*:*)
-	echo hppa64-unknown-linux-${LIBC}
+    ppc64:Linux:*:*)
+	echo powerpc64-unknown-linux-${LIBC}
+	exit ;;
+    ppc:Linux:*:*)
+	echo powerpc-unknown-linux-${LIBC}
+	exit ;;
+    ppc64le:Linux:*:*)
+	echo powerpc64le-unknown-linux-${LIBC}
+	exit ;;
+    ppcle:Linux:*:*)
+	echo powerpcle-unknown-linux-${LIBC}
 	exit ;;
     s390:Linux:*:* | s390x:Linux:*:*)
-	echo ${UNAME_MACHINE}-ibm-linux
+	echo ${UNAME_MACHINE}-ibm-linux-${LIBC}
 	exit ;;
     sh64*:Linux:*:*)
-    	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
     sh*:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
@@ -978,77 +1013,18 @@ EOF
     sparc:Linux:*:* | sparc64:Linux:*:*)
 	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
+    tile*:Linux:*:*)
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	exit ;;
     vax:Linux:*:*)
 	echo ${UNAME_MACHINE}-dec-linux-${LIBC}
 	exit ;;
     x86_64:Linux:*:*)
-	echo x86_64-unknown-linux-${LIBC}
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
     xtensa*:Linux:*:*)
-    	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
+	echo ${UNAME_MACHINE}-unknown-linux-${LIBC}
 	exit ;;
-    i*86:Linux:*:*)
-	# The BFD linker knows what the default object file format is, so
-	# first see if it will tell us. cd to the root directory to prevent
-	# problems with other programs or directories called `ld' in the path.
-	# Set LC_ALL=C to ensure ld outputs messages in English.
-	ld_supported_targets=`cd /; LC_ALL=C ld --help 2>&1 \
-			 | sed -ne '/supported targets:/!d
-				    s/[ 	][ 	]*/ /g
-				    s/.*supported targets: *//
-				    s/ .*//
-				    p'`
-        case "$ld_supported_targets" in
-	  elf32-i386)
-		TENTATIVE="${UNAME_MACHINE}-pc-linux-${LIBC}"
-		;;
-	  a.out-i386-linux)
-		echo "${UNAME_MACHINE}-pc-linux-${LIBC}aout"
-		exit ;;
-	  "")
-		# Either a pre-BFD a.out linker (linux-gnuoldld) or
-		# one that does not give us useful --help.
-		echo "${UNAME_MACHINE}-pc-linux-${LIBC}oldld"
-		exit ;;
-	esac
-	# This should get integrated into the C code below, but now we hack
-	if [ "$LIBC" != "gnu" ] ; then echo "$TENTATIVE" && exit 0 ; fi
-	# Determine whether the default compiler is a.out or elf
-	eval $set_cc_for_build
-	sed 's/^	//' << EOF >$dummy.c
-	#include <features.h>
-	#ifdef __ELF__
-	# ifdef __GLIBC__
-	#  if __GLIBC__ >= 2
-	LIBC=gnu
-	#  else
-	LIBC=gnulibc1
-	#  endif
-	# else
-	LIBC=gnulibc1
-	# endif
-	#else
-	#if defined(__INTEL_COMPILER) || defined(__PGI) || defined(__SUNPRO_C) || defined(__SUNPRO_CC)
-	LIBC=gnu
-	#else
-	LIBC=gnuaout
-	#endif
-	#endif
-	#ifdef __dietlibc__
-	LIBC=dietlibc
-	#endif
-EOF
-	eval "`$CC_FOR_BUILD -E $dummy.c 2>/dev/null | sed -n '
-	    /^LIBC/{
-		s: ::g
-		p
-	    }'`"
-	test x"${LIBC}" != x && {
-		echo "${UNAME_MACHINE}-pc-linux-${LIBC}"
-		exit
-	}
-	test x"${TENTATIVE}" != x && { echo "${TENTATIVE}"; exit; }
-	;;
     i*86:DYNIX/ptx:4*:*)
 	# ptx 4.0 does uname -s correctly, with DYNIX/ptx in there.
 	# earlier versions are messed up and put the nodename in both
@@ -1056,11 +1032,11 @@ EOF
 	echo i386-sequent-sysv4
 	exit ;;
     i*86:UNIX_SV:4.2MP:2.*)
-        # Unixware is an offshoot of SVR4, but it has its own version
-        # number series starting with 2...
-        # I am not positive that other SVR4 systems won't match this,
+	# Unixware is an offshoot of SVR4, but it has its own version
+	# number series starting with 2...
+	# I am not positive that other SVR4 systems won't match this,
 	# I just have to hope.  -- rms.
-        # Use sysv4.2uw... so that sysv4* matches it.
+	# Use sysv4.2uw... so that sysv4* matches it.
 	echo ${UNAME_MACHINE}-pc-sysv4.2uw${UNAME_VERSION}
 	exit ;;
     i*86:OS/2:*:*)
@@ -1077,7 +1053,7 @@ EOF
     i*86:syllable:*:*)
 	echo ${UNAME_MACHINE}-pc-syllable
 	exit ;;
-    i*86:LynxOS:2.*:* | i*86:LynxOS:3.[01]*:* | i*86:LynxOS:4.0*:*)
+    i*86:LynxOS:2.*:* | i*86:LynxOS:3.[01]*:* | i*86:LynxOS:4.[02]*:*)
 	echo i386-unknown-lynxos${UNAME_RELEASE}
 	exit ;;
     i*86:*DOS:*:*)
@@ -1092,7 +1068,7 @@ EOF
 	fi
 	exit ;;
     i*86:*:5:[678]*)
-    	# UnixWare 7.x, OpenUNIX and OpenServer 6.
+	# UnixWare 7.x, OpenUNIX and OpenServer 6.
 	case `/bin/uname -X | grep "^Machine"` in
 	    *486*)	     UNAME_MACHINE=i486 ;;
 	    *Pentium)	     UNAME_MACHINE=i586 ;;
@@ -1120,10 +1096,13 @@ EOF
 	exit ;;
     pc:*:*:*)
 	# Left here for compatibility:
-        # uname -m prints for DJGPP always 'pc', but it prints nothing about
-        # the processor, so we play safe by assuming i386.
-	echo i386-pc-msdosdjgpp
-        exit ;;
+	# uname -m prints for DJGPP always 'pc', but it prints nothing about
+	# the processor, so we play safe by assuming i586.
+	# Note: whatever this is, it MUST be the same as what config.sub
+	# prints for the "djgpp" host, or else GDB configury will decide that
+	# this is a cross-build.
+	echo i586-pc-msdosdjgpp
+	exit ;;
     Intel:Mach:3*:*)
 	echo i386-pc-mach3
 	exit ;;
@@ -1158,8 +1137,18 @@ EOF
 	/bin/uname -p 2>/dev/null | /bin/grep entium >/dev/null \
 	  && { echo i586-ncr-sysv4.3${OS_REL}; exit; } ;;
     3[34]??:*:4.0:* | 3[34]??,*:*:4.0:*)
-        /bin/uname -p 2>/dev/null | grep 86 >/dev/null \
-          && { echo i486-ncr-sysv4; exit; } ;;
+	/bin/uname -p 2>/dev/null | grep 86 >/dev/null \
+	  && { echo i486-ncr-sysv4; exit; } ;;
+    NCR*:*:4.2:* | MPRAS*:*:4.2:*)
+	OS_REL='.3'
+	test -r /etc/.relid \
+	    && OS_REL=.`sed -n 's/[^ ]* [^ ]* \([0-9][0-9]\).*/\1/p' < /etc/.relid`
+	/bin/uname -p 2>/dev/null | grep 86 >/dev/null \
+	    && { echo i486-ncr-sysv4.3${OS_REL}; exit; }
+	/bin/uname -p 2>/dev/null | /bin/grep entium >/dev/null \
+	    && { echo i586-ncr-sysv4.3${OS_REL}; exit; }
+	/bin/uname -p 2>/dev/null | /bin/grep pteron >/dev/null \
+	    && { echo i586-ncr-sysv4.3${OS_REL}; exit; } ;;
     m68*:LynxOS:2.*:* | m68*:LynxOS:3.0*:*)
 	echo m68k-unknown-lynxos${UNAME_RELEASE}
 	exit ;;
@@ -1172,7 +1161,7 @@ EOF
     rs6000:LynxOS:2.*:*)
 	echo rs6000-unknown-lynxos${UNAME_RELEASE}
 	exit ;;
-    PowerPC:LynxOS:2.*:* | PowerPC:LynxOS:3.[01]*:* | PowerPC:LynxOS:4.0*:*)
+    PowerPC:LynxOS:2.*:* | PowerPC:LynxOS:3.[01]*:* | PowerPC:LynxOS:4.[02]*:*)
 	echo powerpc-unknown-lynxos${UNAME_RELEASE}
 	exit ;;
     SM[BE]S:UNIX_SV:*:*)
@@ -1192,10 +1181,10 @@ EOF
 		echo ns32k-sni-sysv
 	fi
 	exit ;;
-    PENTIUM:*:4.0*:*) # Unisys `ClearPath HMP IX 4000' SVR4/MP effort
-                      # says <Richard.M.Bartel@ccMail.Census.GOV>
-        echo i586-unisys-sysv4
-        exit ;;
+    PENTIUM:*:4.0*:*)	# Unisys `ClearPath HMP IX 4000' SVR4/MP effort
+			# says <Richard.M.Bartel@ccMail.Census.GOV>
+	echo i586-unisys-sysv4
+	exit ;;
     *:UNIX_System_V:4*:FTX*)
 	# From Gerald Hewes <hewes@openmarket.com>.
 	# How about differentiating between stratus architectures? -djm
@@ -1221,11 +1210,11 @@ EOF
 	exit ;;
     R[34]000:*System_V*:*:* | R4000:UNIX_SYSV:*:* | R*000:UNIX_SV:*:*)
 	if [ -d /usr/nec ]; then
-	        echo mips-nec-sysv${UNAME_RELEASE}
+		echo mips-nec-sysv${UNAME_RELEASE}
 	else
-	        echo mips-unknown-sysv${UNAME_RELEASE}
+		echo mips-unknown-sysv${UNAME_RELEASE}
 	fi
-        exit ;;
+	exit ;;
     BeBox:BeOS:*:*)	# BeOS running on hardware made by Be, PPC only.
 	echo powerpc-be-beos
 	exit ;;
@@ -1238,6 +1227,9 @@ EOF
     BePC:Haiku:*:*)	# Haiku running on Intel PC compatible.
 	echo i586-pc-haiku
 	exit ;;
+    x86_64:Haiku:*:*)
+	echo x86_64-unknown-haiku
+	exit ;;
     SX-4:SUPER-UX:*:*)
 	echo sx4-nec-superux${UNAME_RELEASE}
 	exit ;;
@@ -1264,9 +1256,31 @@ EOF
 	exit ;;
     *:Darwin:*:*)
 	UNAME_PROCESSOR=`uname -p` || UNAME_PROCESSOR=unknown
-	case $UNAME_PROCESSOR in
-	    unknown) UNAME_PROCESSOR=powerpc ;;
-	esac
+	eval $set_cc_for_build
+	if test "$UNAME_PROCESSOR" = unknown ; then
+	    UNAME_PROCESSOR=powerpc
+	fi
+	if test `echo "$UNAME_RELEASE" | sed -e 's/\..*//'` -le 10 ; then
+	    if [ "$CC_FOR_BUILD" != 'no_compiler_found' ]; then
+		if (echo '#ifdef __LP64__'; echo IS_64BIT_ARCH; echo '#endif') | \
+		    (CCOPTS= $CC_FOR_BUILD -E - 2>/dev/null) | \
+		    grep IS_64BIT_ARCH >/dev/null
+		then
+		    case $UNAME_PROCESSOR in
+			i386) UNAME_PROCESSOR=x86_64 ;;
+			powerpc) UNAME_PROCESSOR=powerpc64 ;;
+		    esac
+		fi
+	    fi
+	elif test "$UNAME_PROCESSOR" = i386 ; then
+	    # Avoid executing cc on OS X 10.9, as it ships with a stub
+	    # that puts up a graphical alert prompting to install
+	    # developer tools.  Any system running Mac OS X 10.7 or
+	    # later (Darwin 11 and later) is required to have a 64-bit
+	    # processor. This is not true of the ARM version of Darwin
+	    # that Apple uses in portable devices.
+	    UNAME_PROCESSOR=x86_64
+	fi
 	echo ${UNAME_PROCESSOR}-apple-darwin${UNAME_RELEASE}
 	exit ;;
     *:procnto*:*:* | *:QNX:[0123456789]*:*)
@@ -1280,7 +1294,10 @@ EOF
     *:QNX:*:4*)
 	echo i386-pc-qnx
 	exit ;;
-    NSE-?:NONSTOP_KERNEL:*:*)
+    NEO-?:NONSTOP_KERNEL:*:*)
+	echo neo-tandem-nsk${UNAME_RELEASE}
+	exit ;;
+    NSE-*:NONSTOP_KERNEL:*:*)
 	echo nse-tandem-nsk${UNAME_RELEASE}
 	exit ;;
     NSR-?:NONSTOP_KERNEL:*:*)
@@ -1325,13 +1342,13 @@ EOF
 	echo pdp10-unknown-its
 	exit ;;
     SEI:*:*:SEIUX)
-        echo mips-sei-seiux${UNAME_RELEASE}
+	echo mips-sei-seiux${UNAME_RELEASE}
 	exit ;;
     *:DragonFly:*:*)
 	echo ${UNAME_MACHINE}-unknown-dragonfly`echo ${UNAME_RELEASE}|sed -e 's/[-(].*//'`
 	exit ;;
     *:*VMS:*:*)
-    	UNAME_MACHINE=`(uname -p) 2>/dev/null`
+	UNAME_MACHINE=`(uname -p) 2>/dev/null`
 	case "${UNAME_MACHINE}" in
 	    A*) echo alpha-dec-vms ; exit ;;
 	    I*) echo ia64-dec-vms ; exit ;;
@@ -1346,158 +1363,13 @@ EOF
     i*86:rdos:*:*)
 	echo ${UNAME_MACHINE}-pc-rdos
 	exit ;;
-esac
-
-#echo '(No uname command or uname output not recognized.)' 1>&2
-#echo "${UNAME_MACHINE}:${UNAME_SYSTEM}:${UNAME_RELEASE}:${UNAME_VERSION}" 1>&2
-
-eval $set_cc_for_build
-cat >$dummy.c <<EOF
-#ifdef _SEQUENT_
-# include <sys/types.h>
-# include <sys/utsname.h>
-#endif
-main ()
-{
-#if defined (sony)
-#if defined (MIPSEB)
-  /* BFD wants "bsd" instead of "newsos".  Perhaps BFD should be changed,
-     I don't know....  */
-  printf ("mips-sony-bsd\n"); exit (0);
-#else
-#include <sys/param.h>
-  printf ("m68k-sony-newsos%s\n",
-#ifdef NEWSOS4
-          "4"
-#else
-	  ""
-#endif
-         ); exit (0);
-#endif
-#endif
-
-#if defined (__arm) && defined (__acorn) && defined (__unix)
-  printf ("arm-acorn-riscix\n"); exit (0);
-#endif
-
-#if defined (hp300) && !defined (hpux)
-  printf ("m68k-hp-bsd\n"); exit (0);
-#endif
-
-#if defined (NeXT)
-#if !defined (__ARCHITECTURE__)
-#define __ARCHITECTURE__ "m68k"
-#endif
-  int version;
-  version=`(hostinfo | sed -n 's/.*NeXT Mach \([0-9]*\).*/\1/p') 2>/dev/null`;
-  if (version < 4)
-    printf ("%s-next-nextstep%d\n", __ARCHITECTURE__, version);
-  else
-    printf ("%s-next-openstep%d\n", __ARCHITECTURE__, version);
-  exit (0);
-#endif
-
-#if defined (MULTIMAX) || defined (n16)
-#if defined (UMAXV)
-  printf ("ns32k-encore-sysv\n"); exit (0);
-#else
-#if defined (CMU)
-  printf ("ns32k-encore-mach\n"); exit (0);
-#else
-  printf ("ns32k-encore-bsd\n"); exit (0);
-#endif
-#endif
-#endif
-
-#if defined (__386BSD__)
-  printf ("i386-pc-bsd\n"); exit (0);
-#endif
-
-#if defined (sequent)
-#if defined (i386)
-  printf ("i386-sequent-dynix\n"); exit (0);
-#endif
-#if defined (ns32000)
-  printf ("ns32k-sequent-dynix\n"); exit (0);
-#endif
-#endif
-
-#if defined (_SEQUENT_)
-    struct utsname un;
-
-    uname(&un);
-
-    if (strncmp(un.version, "V2", 2) == 0) {
-	printf ("i386-sequent-ptx2\n"); exit (0);
-    }
-    if (strncmp(un.version, "V1", 2) == 0) { /* XXX is V1 correct? */
-	printf ("i386-sequent-ptx1\n"); exit (0);
-    }
-    printf ("i386-sequent-ptx\n"); exit (0);
-
-#endif
-
-#if defined (vax)
-# if !defined (ultrix)
-#  include <sys/param.h>
-#  if defined (BSD)
-#   if BSD == 43
-      printf ("vax-dec-bsd4.3\n"); exit (0);
-#   else
-#    if BSD == 199006
-      printf ("vax-dec-bsd4.3reno\n"); exit (0);
-#    else
-      printf ("vax-dec-bsd\n"); exit (0);
-#    endif
-#   endif
-#  else
-    printf ("vax-dec-bsd\n"); exit (0);
-#  endif
-# else
-    printf ("vax-dec-ultrix\n"); exit (0);
-# endif
-#endif
-
-#if defined (alliant) && defined (i860)
-  printf ("i860-alliant-bsd\n"); exit (0);
-#endif
-
-  exit (1);
-}
-EOF
-
-$CC_FOR_BUILD -o $dummy $dummy.c 2>/dev/null && SYSTEM_NAME=`$dummy` &&
-	{ echo "$SYSTEM_NAME"; exit; }
-
-# Apollos put the system type in the environment.
-
-test -d /usr/apollo && { echo ${ISP}-apollo-${SYSTYPE}; exit; }
-
-# Convex versions that predate uname can use getsysinfo(1)
-
-if [ -x /usr/convex/getsysinfo ]
-then
-    case `getsysinfo -f cpu_type` in
-    c1*)
-	echo c1-convex-bsd
-	exit ;;
-    c2*)
-	if getsysinfo -f scalar_acc
-	then echo c32-convex-bsd
-	else echo c2-convex-bsd
-	fi
+    i*86:AROS:*:*)
+	echo ${UNAME_MACHINE}-pc-aros
 	exit ;;
-    c34*)
-	echo c34-convex-bsd
+    x86_64:VMkernel:*:*)
+	echo ${UNAME_MACHINE}-unknown-esx
 	exit ;;
-    c38*)
-	echo c38-convex-bsd
-	exit ;;
-    c4*)
-	echo c4-convex-bsd
-	exit ;;
-    esac
-fi
+esac
 
 cat >&2 <<EOF
 $0: unable to guess system type
diff --git a/scripts/config.sub b/scripts/config.sub
index c042dbadb..092cff00e 100755
--- a/scripts/config.sub
+++ b/scripts/config.sub
@@ -1,44 +1,40 @@
 #! /bin/sh
 # Configuration validation subroutine script.
-#   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
-#   2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
-#   Free Software Foundation, Inc.
+#   Copyright 1992-2014 Free Software Foundation, Inc.
 
-timestamp='2008-09-08'
+timestamp='2014-01-01'
 
-# This file is (in principle) common to ALL GNU software.
-# The presence of a machine in this file suggests that SOME GNU software
-# can handle that machine.  It does not imply ALL GNU software can.
-#
-# This file is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
+# This file is free software; you can redistribute it and/or modify it
+# under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
 # (at your option) any later version.
 #
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-# GNU General Public License for more details.
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# General Public License for more details.
 #
 # You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
-# 02110-1301, USA.
+# along with this program; if not, see <http://www.gnu.org/licenses/>.
 #
 # As a special exception to the GNU General Public License, if you
 # distribute this file as part of a program that contains a
 # configuration script generated by Autoconf, you may include it under
-# the same distribution terms that you use for the rest of that program.
+# the same distribution terms that you use for the rest of that
+# program.  This Exception is an additional permission under section 7
+# of the GNU General Public License, version 3 ("GPLv3").
 
 
-# Please send patches to <config-patches@gnu.org>.  Submit a context
-# diff and a properly formatted ChangeLog entry.
+# Please send patches with a ChangeLog entry to config-patches@gnu.org.
 #
 # Configuration subroutine to validate and canonicalize a configuration type.
 # Supply the specified configuration type as an argument.
 # If it is invalid, we print an error message on stderr and exit with code 1.
 # Otherwise, we print the canonical config type on stdout and succeed.
 
+# You can get the latest version of this script from:
+# http://git.savannah.gnu.org/gitweb/?p=config.git;a=blob_plain;f=config.sub;hb=HEAD
+
 # This file is supposed to be the same for all GNU packages
 # and recognize all the CPU types, system types and aliases
 # that are meaningful with *any* GNU software.
@@ -72,8 +68,7 @@ Report bugs and patches to <config-patches@gnu.org>."
 version="\
 GNU config.sub ($timestamp)
 
-Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
-2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+Copyright 1992-2014 Free Software Foundation, Inc.
 
 This is free software; see the source for copying conditions.  There is NO
 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE."
@@ -120,13 +115,18 @@ esac
 # Here we must recognize all the valid KERNEL-OS combinations.
 maybe_os=`echo $1 | sed 's/^\(.*\)-\([^-]*-[^-]*\)$/\2/'`
 case $maybe_os in
-  nto-qnx* | linux-gnu* | linux-dietlibc | linux-newlib* | linux-uclibc* | \
-  linux-musl* | \
-  uclinux-uclibc* | uclinux-gnu* | kfreebsd*-gnu* | knetbsd*-gnu* | netbsd*-gnu* | \
+  nto-qnx* | linux-gnu* | linux-android* | linux-dietlibc | linux-newlib* | \
+  linux-musl* | linux-uclibc* | uclinux-uclibc* | uclinux-gnu* | kfreebsd*-gnu* | \
+  knetbsd*-gnu* | netbsd*-gnu* | \
+  kopensolaris*-gnu* | \
   storm-chaos* | os2-emx* | rtmk-nova*)
     os=-$maybe_os
     basic_machine=`echo $1 | sed 's/^\(.*\)-\([^-]*-[^-]*\)$/\1/'`
     ;;
+  android-linux)
+    os=-linux-android
+    basic_machine=`echo $1 | sed 's/^\(.*\)-\([^-]*-[^-]*\)$/\1/'`-unknown
+    ;;
   *)
     basic_machine=`echo $1 | sed 's/-[^-]*$//'`
     if [ $basic_machine != $1 ]
@@ -149,10 +149,13 @@ case $os in
 	-convergent* | -ncr* | -news | -32* | -3600* | -3100* | -hitachi* |\
 	-c[123]* | -convex* | -sun | -crds | -omron* | -dg | -ultra | -tti* | \
 	-harris | -dolphin | -highlevel | -gould | -cbm | -ns | -masscomp | \
-	-apple | -axis | -knuth | -cray)
+	-apple | -axis | -knuth | -cray | -microblaze*)
 		os=
 		basic_machine=$1
 		;;
+	-bluegene*)
+		os=-cnk
+		;;
 	-sim | -cisco | -oki | -wec | -winbond)
 		os=
 		basic_machine=$1
@@ -167,10 +170,10 @@ case $os in
 		os=-chorusos
 		basic_machine=$1
 		;;
- 	-chorusrdb)
- 		os=-chorusrdb
+	-chorusrdb)
+		os=-chorusrdb
 		basic_machine=$1
- 		;;
+		;;
 	-hiux*)
 		os=-hiuxwe2
 		;;
@@ -215,6 +218,12 @@ case $os in
 	-isc*)
 		basic_machine=`echo $1 | sed -e 's/86-.*/86-pc/'`
 		;;
+	-lynx*178)
+		os=-lynxos178
+		;;
+	-lynx*5)
+		os=-lynxos5
+		;;
 	-lynx*)
 		os=-lynxos
 		;;
@@ -239,17 +248,26 @@ case $basic_machine in
 	# Some are omitted here because they have special meanings below.
 	1750a | 580 \
 	| a29k \
+	| aarch64 | aarch64_be \
 	| alpha | alphaev[4-8] | alphaev56 | alphaev6[78] | alphapca5[67] \
 	| alpha64 | alpha64ev[4-8] | alpha64ev56 | alpha64ev6[78] | alpha64pca5[67] \
 	| am33_2.0 \
-	| arc | arm | arm[bl]e | arme[lb] | armv[2345] | armv[345][lb] | avr | avr32 \
+	| arc | arceb \
+	| arm | arm[bl]e | arme[lb] | armv[2-8] | armv[3-8][lb] | armv7[arm] \
+	| avr | avr32 \
+	| be32 | be64 \
 	| bfin \
-	| c4x | clipper \
-	| d10v | d30v | dlx | dsp16xx | dvp \
+	| c4x | c8051 | clipper \
+	| d10v | d30v | dlx | dsp16xx \
+	| epiphany \
 	| fido | fr30 | frv \
 	| h8300 | h8500 | hppa | hppa1.[01] | hppa2.0 | hppa2.0[nw] | hppa64 \
+	| hexagon \
 	| i370 | i860 | i960 | ia64 \
 	| ip2k | iq2000 \
+	| k1om \
+	| le32 | le64 \
+	| lm32 \
 	| m32c | m32r | m32rle | m68000 | m68k | m88k \
 	| maxq | mb | microblaze | microblazeel | mcore | mep | metag \
 	| mips | mipsbe | mipseb | mipsel | mipsle \
@@ -269,31 +287,45 @@ case $basic_machine in
 	| mipsisa64r2 | mipsisa64r2el \
 	| mipsisa64sb1 | mipsisa64sb1el \
 	| mipsisa64sr71k | mipsisa64sr71kel \
+	| mipsr5900 | mipsr5900el \
 	| mipstx39 | mipstx39el \
 	| mn10200 | mn10300 \
+	| moxie \
 	| mt \
 	| msp430 \
-	| nios | nios2 \
+	| nds32 | nds32le | nds32be \
+	| nios | nios2 | nios2eb | nios2el \
 	| ns16k | ns32k \
-	| or32 \
+	| open8 \
+	| or1k | or32 \
 	| pdp10 | pdp11 | pj | pjl \
-	| powerpc | powerpc64 | powerpc64le | powerpcle | ppcbe \
+	| powerpc | powerpc64 | powerpc64le | powerpcle \
 	| pyramid \
+	| rl78 | rx \
 	| score \
-	| sh | sh[1234] | sh[24]a | sh[24]a*eb | sh[23]e | sh[34]eb | sheb | shbe | shle | sh[1234]le | sh3ele \
+	| sh | sh[1234] | sh[24]a | sh[24]aeb | sh[23]e | sh[34]eb | sheb | shbe | shle | sh[1234]le | sh3ele \
 	| sh64 | sh64le \
 	| sparc | sparc64 | sparc64b | sparc64v | sparc86x | sparclet | sparclite \
 	| sparcv8 | sparcv9 | sparcv9b | sparcv9v \
-	| spu | strongarm \
-	| tahoe | thumb | tic4x | tic80 | tron \
-	| v850 | v850e \
+	| spu \
+	| tahoe | tic4x | tic54x | tic55x | tic6x | tic80 | tron \
+	| ubicom32 \
+	| v850 | v850e | v850e1 | v850e2 | v850es | v850e2v3 \
 	| we32k \
-	| x86 | xc16x | xscale | xscalee[bl] | xstormy16 | xtensa \
+	| x86 | xc16x | xstormy16 | xtensa \
 	| z8k | z80)
 		basic_machine=$basic_machine-unknown
 		;;
-	m6811 | m68hc11 | m6812 | m68hc12)
-		# Motorola 68HC11/12.
+	c54x)
+		basic_machine=tic54x-unknown
+		;;
+	c55x)
+		basic_machine=tic55x-unknown
+		;;
+	c6x)
+		basic_machine=tic6x-unknown
+		;;
+	m6811 | m68hc11 | m6812 | m68hc12 | m68hcs12x | nvptx | picochip)
 		basic_machine=$basic_machine-unknown
 		os=-none
 		;;
@@ -303,6 +335,21 @@ case $basic_machine in
 		basic_machine=mt-unknown
 		;;
 
+	strongarm | thumb | xscale)
+		basic_machine=arm-unknown
+		;;
+	xgate)
+		basic_machine=$basic_machine-unknown
+		os=-none
+		;;
+	xscaleeb)
+		basic_machine=armeb-unknown
+		;;
+
+	xscaleel)
+		basic_machine=armel-unknown
+		;;
+
 	# We use `pc' rather than `unknown'
 	# because (1) that's what they normally are, and
 	# (2) the word "unknown" tends to confuse beginning users.
@@ -317,24 +364,31 @@ case $basic_machine in
 	# Recognize the basic CPU types with company name.
 	580-* \
 	| a29k-* \
+	| aarch64-* | aarch64_be-* \
 	| alpha-* | alphaev[4-8]-* | alphaev56-* | alphaev6[78]-* \
 	| alpha64-* | alpha64ev[4-8]-* | alpha64ev56-* | alpha64ev6[78]-* \
-	| alphapca5[67]-* | alpha64pca5[67]-* | arc-* \
+	| alphapca5[67]-* | alpha64pca5[67]-* | arc-* | arceb-* \
 	| arm-*  | armbe-* | armle-* | armeb-* | armv*-* \
 	| avr-* | avr32-* \
+	| be32-* | be64-* \
 	| bfin-* | bs2000-* \
-	| c[123]* | c30-* | [cjt]90-* | c4x-* | c54x-* | c55x-* | c6x-* \
-	| clipper-* | craynv-* | cydra-* \
+	| c[123]* | c30-* | [cjt]90-* | c4x-* \
+	| c8051-* | clipper-* | craynv-* | cydra-* \
 	| d10v-* | d30v-* | dlx-* \
 	| elxsi-* \
 	| f30[01]-* | f700-* | fido-* | fr30-* | frv-* | fx80-* \
 	| h8300-* | h8500-* \
 	| hppa-* | hppa1.[01]-* | hppa2.0-* | hppa2.0[nw]-* | hppa64-* \
+	| hexagon-* \
 	| i*86-* | i860-* | i960-* | ia64-* \
 	| ip2k-* | iq2000-* \
+	| k1om-* \
+	| le32-* | le64-* \
+	| lm32-* \
 	| m32c-* | m32r-* | m32rle-* \
 	| m68000-* | m680[012346]0-* | m68360-* | m683?2-* | m68k-* \
 	| m88110-* | m88k-* | maxq-* | mcore-* | metag-* \
+	| microblaze-* | microblazeel-* \
 	| mips-* | mipsbe-* | mipseb-* | mipsel-* | mipsle-* \
 	| mips16-* \
 	| mips64-* | mips64el-* \
@@ -352,28 +406,34 @@ case $basic_machine in
 	| mipsisa64r2-* | mipsisa64r2el-* \
 	| mipsisa64sb1-* | mipsisa64sb1el-* \
 	| mipsisa64sr71k-* | mipsisa64sr71kel-* \
+	| mipsr5900-* | mipsr5900el-* \
 	| mipstx39-* | mipstx39el-* \
 	| mmix-* \
 	| mt-* \
 	| msp430-* \
-	| nios-* | nios2-* \
+	| nds32-* | nds32le-* | nds32be-* \
+	| nios-* | nios2-* | nios2eb-* | nios2el-* \
 	| none-* | np1-* | ns16k-* | ns32k-* \
+	| open8-* \
 	| orion-* \
 	| pdp10-* | pdp11-* | pj-* | pjl-* | pn-* | power-* \
-	| powerpc-* | powerpc64-* | powerpc64le-* | powerpcle-* | ppcbe-* \
+	| powerpc-* | powerpc64-* | powerpc64le-* | powerpcle-* \
 	| pyramid-* \
-	| romp-* | rs6000-* \
-	| sh-* | sh[1234]-* | sh[24]a-* | sh[24]a*eb-* | sh[23]e-* | sh[34]eb-* | sheb-* | shbe-* \
+	| rl78-* | romp-* | rs6000-* | rx-* \
+	| sh-* | sh[1234]-* | sh[24]a-* | sh[24]aeb-* | sh[23]e-* | sh[34]eb-* | sheb-* | shbe-* \
 	| shle-* | sh[1234]le-* | sh3ele-* | sh64-* | sh64le-* \
 	| sparc-* | sparc64-* | sparc64b-* | sparc64v-* | sparc86x-* | sparclet-* \
 	| sparclite-* \
-	| sparcv8-* | sparcv9-* | sparcv9b-* | sparcv9v-* | strongarm-* | sv1-* | sx?-* \
-	| tahoe-* | thumb-* \
-	| tic30-* | tic4x-* | tic54x-* | tic55x-* | tic6x-* | tic80-* | tile-* \
+	| sparcv8-* | sparcv9-* | sparcv9b-* | sparcv9v-* | sv1-* | sx?-* \
+	| tahoe-* \
+	| tic30-* | tic4x-* | tic54x-* | tic55x-* | tic6x-* | tic80-* \
+	| tile*-* \
 	| tron-* \
-	| v850-* | v850e-* | vax-* \
+	| ubicom32-* \
+	| v850-* | v850e-* | v850e1-* | v850es-* | v850e2-* | v850e2v3-* \
+	| vax-* \
 	| we32k-* \
-	| x86-* | x86_64-* | xc16x-* | xps100-* | xscale-* | xscalee[bl]-* \
+	| x86-* | x86_64-* | xc16x-* | xps100-* \
 	| xstormy16-* | xtensa*-* \
 	| ymp-* \
 	| z8k-* | z80-*)
@@ -398,7 +458,7 @@ case $basic_machine in
 		basic_machine=a29k-amd
 		os=-udi
 		;;
-    	abacus)
+	abacus)
 		basic_machine=abacus-unknown
 		;;
 	adobe68k)
@@ -444,6 +504,10 @@ case $basic_machine in
 		basic_machine=m68k-apollo
 		os=-bsd
 		;;
+	aros)
+		basic_machine=i386-pc
+		os=-aros
+		;;
 	aux)
 		basic_machine=m68k-apple
 		os=-aux
@@ -460,11 +524,24 @@ case $basic_machine in
 		basic_machine=bfin-`echo $basic_machine | sed 's/^[^-]*-//'`
 		os=-linux
 		;;
+	bluegene*)
+		basic_machine=powerpc-ibm
+		os=-cnk
+		;;
+	c54x-*)
+		basic_machine=tic54x-`echo $basic_machine | sed 's/^[^-]*-//'`
+		;;
+	c55x-*)
+		basic_machine=tic55x-`echo $basic_machine | sed 's/^[^-]*-//'`
+		;;
+	c6x-*)
+		basic_machine=tic6x-`echo $basic_machine | sed 's/^[^-]*-//'`
+		;;
 	c90)
 		basic_machine=c90-cray
 		os=-unicos
 		;;
-        cegcc)
+	cegcc)
 		basic_machine=arm-unknown
 		os=-cegcc
 		;;
@@ -496,7 +573,7 @@ case $basic_machine in
 		basic_machine=craynv-cray
 		os=-unicosmp
 		;;
-	cr16)
+	cr16 | cr16-*)
 		basic_machine=cr16-unknown
 		os=-elf
 		;;
@@ -654,7 +731,6 @@ case $basic_machine in
 	i370-ibm* | ibm*)
 		basic_machine=i370-ibm
 		;;
-# I'm not sure what "Sysv32" means.  Should this be sysv3.2?
 	i*86v32)
 		basic_machine=`echo $1 | sed -e 's/86.*/86-pc/'`
 		os=-sysv32
@@ -715,8 +791,12 @@ case $basic_machine in
 	microblaze*)
 		basic_machine=microblaze-xilinx
 		;;
+	mingw64)
+		basic_machine=x86_64-pc
+		os=-mingw64
+		;;
 	mingw32)
-		basic_machine=i386-pc
+		basic_machine=i686-pc
 		os=-mingw32
 		;;
 	mingw32ce)
@@ -730,24 +810,6 @@ case $basic_machine in
 		basic_machine=m68k-atari
 		os=-mint
 		;;
-	mipsEE* | ee | ps2)
-		basic_machine=mips64r5900el-scei
-		case $os in
-		    -linux*)
-			;;
-		    *)
-			os=-elf
-			;;
-		esac
-		;;
-	iop)
-		basic_machine=mipsel-scei
-		os=-irx
-		;;
-	dvp)
-		basic_machine=dvp-scei
-		os=-elf
-		;;
 	mips3*-*)
 		basic_machine=`echo $basic_machine | sed -e 's/mips3/mips64/'`
 		;;
@@ -769,10 +831,18 @@ case $basic_machine in
 	ms1-*)
 		basic_machine=`echo $basic_machine | sed -e 's/ms1-/mt-/'`
 		;;
+	msys)
+		basic_machine=i686-pc
+		os=-msys
+		;;
 	mvs)
 		basic_machine=i370-ibm
 		os=-mvs
 		;;
+	nacl)
+		basic_machine=le32-unknown
+		os=-nacl
+		;;
 	ncr3000)
 		basic_machine=i486-ncr
 		os=-sysv4
@@ -837,6 +907,12 @@ case $basic_machine in
 	np1)
 		basic_machine=np1-gould
 		;;
+	neo-tandem)
+		basic_machine=neo-tandem
+		;;
+	nse-tandem)
+		basic_machine=nse-tandem
+		;;
 	nsr-tandem)
 		basic_machine=nsr-tandem
 		;;
@@ -919,9 +995,10 @@ case $basic_machine in
 		;;
 	power)	basic_machine=power-ibm
 		;;
-	ppc)	basic_machine=powerpc-unknown
+	ppc | ppcbe)	basic_machine=powerpc-unknown
 		;;
-	ppc-*)	basic_machine=powerpc-`echo $basic_machine | sed 's/^[^-]*-//'`
+	ppc-* | ppcbe-*)
+		basic_machine=powerpc-`echo $basic_machine | sed 's/^[^-]*-//'`
 		;;
 	ppcle | powerpclittle | ppc-le | powerpc-little)
 		basic_machine=powerpcle-unknown
@@ -946,7 +1023,11 @@ case $basic_machine in
 		basic_machine=i586-unknown
 		os=-pw32
 		;;
-	rdos)
+	rdos | rdos64)
+		basic_machine=x86_64-pc
+		os=-rdos
+		;;
+	rdos32)
 		basic_machine=i386-pc
 		os=-rdos
 		;;
@@ -1015,6 +1096,9 @@ case $basic_machine in
 		basic_machine=i860-stratus
 		os=-sysv4
 		;;
+	strongarm-* | thumb-*)
+		basic_machine=arm-`echo $basic_machine | sed 's/^[^-]*-//'`
+		;;
 	sun2)
 		basic_machine=m68000-sun
 		;;
@@ -1071,20 +1155,8 @@ case $basic_machine in
 		basic_machine=t90-cray
 		os=-unicos
 		;;
-	tic54x | c54x*)
-		basic_machine=tic54x-unknown
-		os=-coff
-		;;
-	tic55x | c55x*)
-		basic_machine=tic55x-unknown
-		os=-coff
-		;;
-	tic6x | c6x*)
-		basic_machine=tic6x-unknown
-		os=-coff
-		;;
 	tile*)
-		basic_machine=tile-unknown
+		basic_machine=$basic_machine-unknown
 		os=-linux-gnu
 		;;
 	tx39)
@@ -1154,6 +1226,9 @@ case $basic_machine in
 	xps | xps100)
 		basic_machine=xps100-honeywell
 		;;
+	xscale-* | xscalee[bl]-*)
+		basic_machine=`echo $basic_machine | sed 's/^xscale/arm/'`
+		;;
 	ymp)
 		basic_machine=ymp-cray
 		os=-unicos
@@ -1204,7 +1279,7 @@ case $basic_machine in
 	we32k)
 		basic_machine=we32k-att
 		;;
-	sh[1234] | sh[24]a | sh[34]eb | sh[1234]le | sh[23]ele)
+	sh[1234] | sh[24]a | sh[24]aeb | sh[34]eb | sh[1234]le | sh[23]ele)
 		basic_machine=sh-unknown
 		;;
 	sparc | sparcv8 | sparcv9 | sparcv9b | sparcv9v)
@@ -1251,9 +1326,12 @@ esac
 if [ x"$os" != x"" ]
 then
 case $os in
-        # First match some system type aliases
-        # that might get confused with valid system types.
+	# First match some system type aliases
+	# that might get confused with valid system types.
 	# -solaris* is a basic system type, with this one exception.
+	-auroraux)
+		os=-auroraux
+		;;
 	-solaris1 | -solaris1.*)
 		os=`echo $os | sed -e 's|solaris1|sunos4|'`
 		;;
@@ -1274,21 +1352,23 @@ case $os in
 	# Each alternative MUST END IN A *, to match a version number.
 	# -sysv* is not here because it comes later, after sysvr4.
 	-gnu* | -bsd* | -mach* | -minix* | -genix* | -ultrix* | -irix* \
-	      | -*vms* | -sco* | -esix* | -isc* | -aix* | -sunos | -sunos[34]*\
-	      | -hpux* | -unos* | -osf* | -luna* | -dgux* | -solaris* | -sym* \
+	      | -*vms* | -sco* | -esix* | -isc* | -aix* | -cnk* | -sunos | -sunos[34]*\
+	      | -hpux* | -unos* | -osf* | -luna* | -dgux* | -auroraux* | -solaris* \
+	      | -sym* | -kopensolaris* | -plan9* \
 	      | -amigaos* | -amigados* | -msdos* | -newsos* | -unicos* | -aof* \
-	      | -aos* \
+	      | -aos* | -aros* \
 	      | -nindy* | -vxsim* | -vxworks* | -ebmon* | -hms* | -mvs* \
 	      | -clix* | -riscos* | -uniplus* | -iris* | -rtu* | -xenix* \
 	      | -hiux* | -386bsd* | -knetbsd* | -mirbsd* | -netbsd* \
-	      | -openbsd* | -solidbsd* \
+	      | -bitrig* | -openbsd* | -solidbsd* \
 	      | -ekkobsd* | -kfreebsd* | -freebsd* | -riscix* | -lynxos* \
 	      | -bosx* | -nextstep* | -cxux* | -aout* | -elf* | -oabi* \
 	      | -ptx* | -coff* | -ecoff* | -winnt* | -domain* | -vsta* \
 	      | -udi* | -eabi* | -lites* | -ieee* | -go32* | -aux* \
 	      | -chorusos* | -chorusrdb* | -cegcc* \
-	      | -cygwin* | -pe* | -psos* | -moss* | -proelf* | -rtems* \
-	      | -mingw32* | -linux-gnu* | -linux-newlib* | -linux-uclibc* | -linux-musl* \
+	      | -cygwin* | -msys* | -pe* | -psos* | -moss* | -proelf* | -rtems* \
+	      | -mingw32* | -mingw64* | -linux-gnu* | -linux-android* \
+	      | -linux-newlib* | -linux-musl* | -linux-uclibc* \
 	      | -uxpv* | -beos* | -mpeix* | -udk* \
 	      | -interix* | -uwin* | -mks* | -rhapsody* | -darwin* | -opened* \
 	      | -openstep* | -oskit* | -conix* | -pw32* | -nonstopux* \
@@ -1296,7 +1376,7 @@ case $os in
 	      | -os2* | -vos* | -palmos* | -uclinux* | -nucleus* \
 	      | -morphos* | -superux* | -rtmk* | -rtmk-nova* | -windiss* \
 	      | -powermax* | -dnix* | -nx6 | -nx7 | -sei* | -dragonfly* \
-	      | -skyos* | -haiku* | -rdos* | -toppers* | -drops* | -irx*)
+	      | -skyos* | -haiku* | -rdos* | -toppers* | -drops* | -es*)
 	# Remember, each alternative MUST END IN *, to match a version number.
 		;;
 	-qnx*)
@@ -1335,7 +1415,7 @@ case $os in
 	-opened*)
 		os=-openedition
 		;;
-        -os400*)
+	-os400*)
 		os=-os400
 		;;
 	-wince*)
@@ -1384,7 +1464,7 @@ case $os in
 	-sinix*)
 		os=-sysv4
 		;;
-        -tpf*)
+	-tpf*)
 		os=-tpf
 		;;
 	-triton*)
@@ -1420,15 +1500,14 @@ case $os in
 	-aros*)
 		os=-aros
 		;;
-	-kaos*)
-		os=-kaos
-		;;
 	-zvmoe)
 		os=-zvmoe
 		;;
 	-dicos*)
 		os=-dicos
 		;;
+	-nacl*)
+		;;
 	-none)
 		;;
 	*)
@@ -1451,10 +1530,10 @@ else
 # system, and we'll never get to this point.
 
 case $basic_machine in
-        score-*)
+	score-*)
 		os=-elf
 		;;
-        spu-*)
+	spu-*)
 		os=-elf
 		;;
 	*-acorn)
@@ -1466,8 +1545,23 @@ case $basic_machine in
 	arm*-semi)
 		os=-aout
 		;;
-        c4x-* | tic4x-*)
-        	os=-coff
+	c4x-* | tic4x-*)
+		os=-coff
+		;;
+	c8051-*)
+		os=-elf
+		;;
+	hexagon-*)
+		os=-elf
+		;;
+	tic54x-*)
+		os=-coff
+		;;
+	tic55x-*)
+		os=-coff
+		;;
+	tic6x-*)
+		os=-coff
 		;;
 	# This must come before the *-dec entry.
 	pdp10-*)
@@ -1487,14 +1581,11 @@ case $basic_machine in
 		;;
 	m68000-sun)
 		os=-sunos3
-		# This also exists in the configure program, but was not the
-		# default.
-		# os=-sunos4
 		;;
 	m68*-cisco)
 		os=-aout
 		;;
-        mep-*)
+	mep-*)
 		os=-elf
 		;;
 	mips*-cisco)
@@ -1503,6 +1594,9 @@ case $basic_machine in
 	mips*-*)
 		os=-elf
 		;;
+	or1k-*)
+		os=-elf
+		;;
 	or32-*)
 		os=-coff
 		;;
@@ -1521,7 +1615,7 @@ case $basic_machine in
 	*-ibm)
 		os=-aix
 		;;
-    	*-knuth)
+	*-knuth)
 		os=-mmixware
 		;;
 	*-wec)
@@ -1626,7 +1720,7 @@ case $basic_machine in
 			-sunos*)
 				vendor=sun
 				;;
-			-aix*)
+			-cnk*|-aix*)
 				vendor=ibm
 				;;
 			-beos*)