fastcopy.c

/*********************************************************************
  Blosc - Blocked Shuffling and Compression Library

  Author: Francesc Alted <francesc@blosc.org>
  Creation date: 2018-01-03

  See LICENSE.txt for details about copyright and rights to use.
**********************************************************************/

/*********************************************************************
  The code in this file is heavily based on memcopy.h, from the

  zlib-ng compression library.  See LICENSES/ZLIB-NG.txt for details.
  See also: https://github.com/zlib-ng/zlib-ng/blob/develop/zlib.h.in

  New implementations by Francesc Alted:
    * fast_copy() and copy_run() functions
    * Support for SSE2/AVX2 copy instructions for these routines
**********************************************************************/

#include <assert.h>
#include "blosc-common.h"

/*
 * Use inlined functions for supported systems.
 */
#if defined(_MSC_VER) && !defined(__cplusplus)   /* Visual Studio */
#define inline __inline  /* Visual C is not C99, but supports some kind of inline */
#endif


static inline unsigned char *copy_1_bytes(unsigned char *out, const unsigned char *from) {
  *out++ = *from;
  return out;
}

static inline unsigned char *copy_2_bytes(unsigned char *out, const unsigned char *from) {
#if defined(BLOSC_STRICT_ALIGN)
  uint16_t chunk;
  memcpy(&chunk, from, 2);
  memcpy(out, &chunk, 2);
#else
  *(uint16_t *) out = *(uint16_t *) from;
#endif
  return out + 2;
}

static inline unsigned char *copy_3_bytes(unsigned char *out, const unsigned char *from) {
  out = copy_1_bytes(out, from);
  return copy_2_bytes(out, from + 1);
}

static inline unsigned char *copy_4_bytes(unsigned char *out, const unsigned char *from) {
#if defined(BLOSC_STRICT_ALIGN)
  uint32_t chunk;
  memcpy(&chunk, from, 4);
  memcpy(out, &chunk, 4);
#else
  *(uint32_t *) out = *(uint32_t *) from;
#endif
  return out + 4;
}

static inline unsigned char *copy_5_bytes(unsigned char *out, const unsigned char *from) {
  out = copy_1_bytes(out, from);
  return copy_4_bytes(out, from + 1);
}

static inline unsigned char *copy_6_bytes(unsigned char *out, const unsigned char *from) {
  out = copy_2_bytes(out, from);
  return copy_4_bytes(out, from + 2);
}

static inline unsigned char *copy_7_bytes(unsigned char *out, const unsigned char *from) {
  out = copy_3_bytes(out, from);
  return copy_4_bytes(out, from + 3);
}

static inline unsigned char *copy_8_bytes(unsigned char *out, const unsigned char *from) {
#if defined(BLOSC_STRICT_ALIGN)
  uint64_t chunk;
  memcpy(&chunk, from, 8);
  memcpy(out, &chunk, 8);
#else
  *(uint64_t *) out = *(uint64_t *) from;
#endif
  return out + 8;
}


static inline unsigned char *copy_16_bytes(unsigned char *out, const unsigned char *from) {
#if defined(__SSE2__)
  __m128i chunk;
  chunk = _mm_loadu_si128((__m128i*)from);
  _mm_storeu_si128((__m128i*)out, chunk);
  out += 16;
#elif !defined(BLOSC_STRICT_ALIGN)
  *(uint64_t*)out = *(uint64_t*)from;
   from += 8; out += 8;
   *(uint64_t*)out = *(uint64_t*)from;
   from += 8; out += 8;
#else
   int i;
   for (i = 0; i < 16; i++) {
     *out++ = *from++;
   }
#endif
  return out;
}

static inline unsigned char *copy_32_bytes(unsigned char *out, const unsigned char *from) {
#if defined(__AVX2__)
  __m256i chunk;
  chunk = _mm256_loadu_si256((__m256i*)from);
  _mm256_storeu_si256((__m256i*)out, chunk);
  out += 32;
#elif defined(__SSE2__)
  __m128i chunk;
  chunk = _mm_loadu_si128((__m128i*)from);
  _mm_storeu_si128((__m128i*)out, chunk);
  from += 16; out += 16;
  chunk = _mm_loadu_si128((__m128i*)from);
  _mm_storeu_si128((__m128i*)out, chunk);
  out += 16;
#elif !defined(BLOSC_STRICT_ALIGN)
  *(uint64_t*)out = *(uint64_t*)from;
  from += 8; out += 8;
  *(uint64_t*)out = *(uint64_t*)from;
  from += 8; out += 8;
  *(uint64_t*)out = *(uint64_t*)from;
  from += 8; out += 8;
  *(uint64_t*)out = *(uint64_t*)from;
  from += 8; out += 8;
#else
  int i;
  for (i = 0; i < 32; i++) {
    *out++ = *from++;
  }
#endif
  return out;
}

// This is never used, so comment it out
//#if defined(__AVX2__)
//static inline unsigned char *copy_32_bytes_aligned(unsigned char *out, const unsigned char *from) {
//  __m256i chunk;
//  chunk = _mm256_load_si256((__m256i*)from);
//  _mm256_storeu_si256((__m256i*)out, chunk);
//  return out + 32;
//}
//#endif  // __AVX2__

/* Copy LEN bytes (7 or fewer) from FROM into OUT. Return OUT + LEN. */
static inline unsigned char *copy_bytes(unsigned char *out, const unsigned char *from, unsigned len) {
  assert(len < 8);

#ifdef BLOSC_STRICT_ALIGN
  while (len--) {
    *out++ = *from++;
  }
#else
  switch (len) {
    case 7:
      return copy_7_bytes(out, from);
    case 6:
      return copy_6_bytes(out, from);
    case 5:
      return copy_5_bytes(out, from);
    case 4:
      return copy_4_bytes(out, from);
    case 3:
      return copy_3_bytes(out, from);
    case 2:
      return copy_2_bytes(out, from);
    case 1:
      return copy_1_bytes(out, from);
    case 0:
      return out;
    default:
      assert(0);
  }
#endif /* BLOSC_STRICT_ALIGN */
  return out;
}

// Define a symbol for avoiding fall-through warnings emitted by gcc >= 7.0
#if ((defined(__GNUC__) && BLOSC_GCC_VERSION >= 700) && !defined(__clang__) && \
     !defined(__ICC) && !defined(__ICL))
#define AVOID_FALLTHROUGH_WARNING
#endif

/* Byte by byte semantics: copy LEN bytes from FROM and write them to OUT. Return OUT + LEN. */
static inline unsigned char *chunk_memcpy(unsigned char *out, const unsigned char *from, unsigned len) {
  unsigned sz = sizeof(uint64_t);
  unsigned rem = len % sz;
  unsigned by8;

  assert(len >= sz);

  /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */
  copy_8_bytes(out, from);

  len /= sz;
  out += rem;
  from += rem;

  by8 = len % 8;
  len -= by8;
  switch (by8) {
    case 7:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));  // Shut-up -Wimplicit-fallthrough warning in GCC
      #endif
    case 6:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    case 5:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    case 4:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    case 3:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    case 2:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    case 1:
      out = copy_8_bytes(out, from);
      from += sz;
      #ifdef AVOID_FALLTHROUGH_WARNING
      __attribute__ ((fallthrough));
      #endif
    default:
      break;
  }

  while (len) {
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;
    out = copy_8_bytes(out, from);
    from += sz;

    len -= 8;
  }

  return out;
}

#if (defined(__SSE2__) && defined(__AVX2__))
/* 16-byte version of chunk_memcpy() */
static inline unsigned char *chunk_memcpy_16(unsigned char *out, const unsigned char *from, unsigned len) {
  unsigned sz = 16;
  unsigned rem = len % sz;
  unsigned ilen;

  assert(len >= sz);

  /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */
  copy_16_bytes(out, from);

  len /= sz;
  out += rem;
  from += rem;

  for (ilen = 0; ilen < len; ilen++) {
    copy_16_bytes(out, from);
    out += sz;
    from += sz;
  }

  return out;
}
#endif


// NOTE: chunk_memcpy_32() and chunk_memcpy_32_unrolled() are not used, so commenting them

///* 32-byte version of chunk_memcpy() */
//static inline unsigned char *chunk_memcpy_32(unsigned char *out, const unsigned char *from, unsigned len) {
//  unsigned sz = 32;
//  unsigned rem = len % sz;
//  unsigned ilen;
//
//  assert(len >= sz);
//
//  /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */
//  copy_32_bytes(out, from);
//
//  len /= sz;
//  out += rem;
//  from += rem;
//
//  for (ilen = 0; ilen < len; ilen++) {
//    copy_32_bytes(out, from);
//    out += sz;
//    from += sz;
//  }
//
//  return out;
//}
//
///* 32-byte *unrolled* version of chunk_memcpy() */
//static inline unsigned char *chunk_memcpy_32_unrolled(unsigned char *out, const unsigned char *from, unsigned len) {
//  unsigned sz = 32;
//  unsigned rem = len % sz;
//  unsigned by8;
//
//  assert(len >= sz);
//
//  /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */
//  copy_32_bytes(out, from);
//
//  len /= sz;
//  out += rem;
//  from += rem;
//
//  by8 = len % 8;
//  len -= by8;
//  switch (by8) {
//    case 7:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 6:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 5:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 4:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 3:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 2:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    case 1:
//      out = copy_32_bytes(out, from);
//      from += sz;
//    default:
//      break;
//  }
//
//  while (len) {
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//    out = copy_32_bytes(out, from);
//    from += sz;
//
//    len -= 8;
//  }
//
//  return out;
//}


/* SSE2/AVX2 *unaligned* version of chunk_memcpy() */
#if defined(__SSE2__) || defined(__AVX2__)
static inline unsigned char *chunk_memcpy_unaligned(unsigned char *out, const unsigned char *from, unsigned len) {
#if defined(__AVX2__)
  unsigned sz = sizeof(__m256i);
#elif defined(__SSE2__)
  unsigned sz = sizeof(__m128i);
#endif
  unsigned rem = len % sz;
  unsigned ilen;

  assert(len >= sz);

  /* Copy a few bytes to make sure the loop below has a multiple of SZ bytes to be copied. */
#if defined(__AVX2__)
  copy_32_bytes(out, from);
#elif defined(__SSE2__)
  copy_16_bytes(out, from);
#endif

  len /= sz;
  out += rem;
  from += rem;

  for (ilen = 0; ilen < len; ilen++) {
#if defined(__AVX2__)
    copy_32_bytes(out, from);
#elif defined(__SSE2__)
    copy_16_bytes(out, from);
#endif
    out += sz;
    from += sz;
  }

  return out;
}
#endif // __SSE2__ || __AVX2__


// NOTE: chunk_memcpy_aligned() is not used, so commenting it

//#if defined(__SSE2__) || defined(__AVX2__)
///* SSE2/AVX2 *aligned* version of chunk_memcpy() */
//static inline unsigned char *chunk_memcpy_aligned(unsigned char *out, const unsigned char *from, unsigned len) {
//#if defined(__AVX2__)
//  unsigned sz = sizeof(__m256i);
//  __m256i chunk;
//#elif defined(__SSE2__)
//  unsigned sz = sizeof(__m128i);
//  __m128i chunk;
//#endif
//  unsigned bytes_to_align = sz - (unsigned)(((uintptr_t)(const void *)(from)) % sz);
//  unsigned corrected_len = len - bytes_to_align;
//  unsigned rem = corrected_len % sz;
//  unsigned ilen;
//
//  assert(len >= sz);
//
//  /* Copy a few bytes to make sure the loop below has aligned access. */
//#if defined(__AVX2__)
//  chunk = _mm256_loadu_si256((__m256i *) from);
//  _mm256_storeu_si256((__m256i *) out, chunk);
//#elif defined(__SSE2__)
//  chunk = _mm_loadu_si128((__m128i *) from);
//  _mm_storeu_si128((__m128i *) out, chunk);
//#endif
//  out += bytes_to_align;
//  from += bytes_to_align;
//
//  len = corrected_len / sz;
//  for (ilen = 0; ilen < len; ilen++) {
//#if defined(__AVX2__)
//    chunk = _mm256_load_si256((__m256i *) from);  /* *aligned* load */
//    _mm256_storeu_si256((__m256i *) out, chunk);
//#elif defined(__SSE2__)
//    chunk = _mm_load_si128((__m128i *) from);  /* *aligned* load */
//    _mm_storeu_si128((__m128i *) out, chunk);
//#endif
//    out += sz;
//    from += sz;
//  }
//
//  /* Copy remaining bytes */
//  if (rem < 8) {
//    out = copy_bytes(out, from, rem);
//  }
//  else {
//    out = chunk_memcpy(out, from, rem);
//  }
//
//  return out;
//}
//#endif // __AVX2__ || __SSE2__


/* Byte by byte semantics: copy LEN bytes from FROM and write them to OUT. Return OUT + LEN. */
unsigned char *fastcopy(unsigned char *out, const unsigned char *from, unsigned len) {
  switch (len) {
    case 32:
      return copy_32_bytes(out, from);
    case 16:
      return copy_16_bytes(out, from);
    case 8:
      return copy_8_bytes(out, from);
    default: {
    }
  }
  if (len < 8) {
    return copy_bytes(out, from, len);
  }
#if defined(__SSE2__)
  if (len < 16) {
    return chunk_memcpy(out, from, len);
  }
#if !defined(__AVX2__)
  return chunk_memcpy_unaligned(out, from, len);
#else
  if (len < 32) {
    return chunk_memcpy_16(out, from, len);
  }
  return chunk_memcpy_unaligned(out, from, len);
#endif  // !__AVX2__
#else
  return chunk_memcpy(out, from, len);
#endif  // __SSE2__
}


/* Copy a run */
unsigned char* copy_match(unsigned char *out, const unsigned char *from, unsigned len) {
#if defined(__AVX2__)
  unsigned sz = sizeof(__m256i);
#elif defined(__SSE2__)
  unsigned sz = sizeof(__m128i);
#else
  unsigned sz = sizeof(uint64_t);
#endif

#if ((defined(__GNUC__) && BLOSC_GCC_VERSION < 800) && !defined(__clang__) && !defined(__ICC) && !defined(__ICL))
  // GCC < 8 in fully optimization mode seems to have problems with the code further below so stop here
  for (; len > 0; len--) {
    *out++ = *from++;
  }
  return out;
#endif

  // If out and from are away more than the size of the copy, then a fastcopy is safe
  unsigned overlap_dist = (unsigned) (out - from);
  if (overlap_dist > sz) {
    return fastcopy(out, from, len);
  }

  // Otherwise we need to be more careful so as not to overwrite destination
  switch (overlap_dist) {
    case 32:
      for (; len >= 32; len -= 32) {
        out = copy_32_bytes(out, from);
      }
      break;
    case 30:
      for (; len >= 30; len -= 30) {
        out = copy_16_bytes(out, from);
        out = copy_8_bytes(out, from + 16);
        out = copy_4_bytes(out, from + 24);
        out = copy_2_bytes(out, from + 28);
      }
      break;
    case 28:
      for (; len >= 28; len -= 28) {
        out = copy_16_bytes(out, from);
        out = copy_8_bytes(out, from + 16);
        out = copy_4_bytes(out, from + 24);
      }
      break;
    case 26:
      for (; len >= 26; len -= 26) {
        out = copy_16_bytes(out, from);
        out = copy_8_bytes(out, from + 16);
        out = copy_2_bytes(out, from + 24);
      }
      break;
    case 24:
      for (; len >= 24; len -= 24) {
        out = copy_16_bytes(out, from);
        out = copy_8_bytes(out, from + 16);
      }
      break;
    case 22:
      for (; len >= 22; len -= 22) {
        out = copy_16_bytes(out, from);
        out = copy_4_bytes(out, from + 16);
        out = copy_2_bytes(out, from + 20);
      }
      break;
    case 20:
      for (; len >= 20; len -= 20) {
        out = copy_16_bytes(out, from);
        out = copy_4_bytes(out, from + 16);
      }
      break;
    case 18:
      for (; len >= 18; len -= 18) {
        out = copy_16_bytes(out, from);
        out = copy_2_bytes(out, from + 16);
      }
      break;
    case 16:
      for (; len >= 16; len -= 16) {
        out = copy_16_bytes(out, from);
      }
      break;
    case 8:
      for (; len >= 8; len -= 8) {
        out = copy_8_bytes(out, from);
      }
      break;
    case 4:
      for (; len >= 4; len -= 4) {
        out = copy_4_bytes(out, from);
      }
      break;
    case 2:
      for (; len >= 2; len -= 2) {
        out = copy_2_bytes(out, from);
      }
      break;
    default:
      for (; len > 0; len--) {
        *out++ = *from++;
      }
  }

  // Copy the leftovers
  for (; len > 0; len--) {
    *out++ = *from++;
  }

  return out;
}