<commit_before>// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Contains utils for reading, writing and debug printing bit streams.

#ifndef LIBSPIRV_UTIL_BIT_STREAM_H_
#define LIBSPIRV_UTIL_BIT_STREAM_H_

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <functional>
#include <sstream>
#include <string>
#include <vector>

namespace spvutils {

// Returns rounded down log2(val). log2(0) is considered 0.
size_t Log2U64(uint64_t val);

// Terminology:
// Bits - usually used for a uint64 word, first bit is the lowest.
// Stream - std::string of '0' and '1', read left-to-right,
//          i.e. first bit is at the front and not at the end as in
//          std::bitset::to_string().
// Bitset - std::bitset corresponding to uint64 bits and to reverse(stream).

// Converts number of bits to a respective number of chunks of size N.
// For example NumBitsToNumWords<8> returns how many bytes are needed to store
// |num_bits|.
template <size_t N>
inline size_t NumBitsToNumWords(size_t num_bits) {
  return (num_bits + (N - 1)) / N;
}

// Returns value of the same type as |in|, where all but the first |num_bits|
// are set to zero.
template <typename T>
inline T GetLowerBits(T in, size_t num_bits) {
  return sizeof(T) * 8 == num_bits ? in : in & T((T(1) << num_bits) - T(1));
}

// Encodes signed integer as unsigned in zigzag order:
//  0 -> 0
// -1 -> 1
//  1 -> 2
// -2 -> 3
//  2 -> 4
// Motivation: -1 is 0xFF...FF what doesn't work very well with
// WriteVariableWidth which prefers to have as many 0 bits as possible.
inline uint64_t EncodeZigZag(int64_t val) { return (val << 1) ^ (val >> 63); }

// Decodes signed integer encoded with EncodeZigZag.
inline int64_t DecodeZigZag(uint64_t val) {
  if (val & 1) {
    // Negative.
    // 1 -> -1
    // 3 -> -2
    // 5 -> -3
    return -1 - (val >> 1);
  } else {
    // Non-negative.
    // 0 -> 0
    // 2 -> 1
    // 4 -> 2
    return val >> 1;
  }
}

// Encodes signed integer as unsigned. This is a generalized version of
// EncodeZigZag, designed to favor small positive numbers.
// Values are transformed in blocks of 2^|block_exponent|.
// If |block_exponent| is zero, then this degenerates into normal EncodeZigZag.
// Example when |block_exponent| is 1 (return value is the index):
// 0, 1, -1, -2, 2, 3, -3, -4, 4, 5, -5, -6, 6, 7, -7, -8
// Example when |block_exponent| is 2:
// 0, 1, 2, 3, -1, -2, -3, -4, 4, 5, 6, 7, -5, -6, -7, -8
inline uint64_t EncodeZigZag(int64_t val, size_t block_exponent) {
  assert(block_exponent < 64);
  const uint64_t uval = static_cast<uint64_t>(val >= 0 ? val : -val - 1);
  const uint64_t block_num =
      ((uval >> block_exponent) << 1) + (val >= 0 ? 0 : 1);
  const uint64_t pos = GetLowerBits(uval, block_exponent);
  return (block_num << block_exponent) + pos;
}

// Decodes signed integer encoded with EncodeZigZag. |block_exponent| must be
// the same.
inline int64_t DecodeZigZag(uint64_t val, size_t block_exponent) {
  assert(block_exponent < 64);
  const uint64_t block_num = val >> block_exponent;
  const uint64_t pos = GetLowerBits(val, block_exponent);
  if (block_num & 1) {
    // Negative.
    return -1LL - ((block_num >> 1) << block_exponent) - pos;
  } else {
    // Positive.
    return ((block_num >> 1) << block_exponent) + pos;
  }
}

// Converts |buffer| to a stream of '0' and '1'.
template <typename T>
std::string BufferToStream(const std::vector<T>& buffer) {
  std::stringstream ss;
  for (auto it = buffer.begin(); it != buffer.end(); ++it) {
    std::string str = std::bitset<sizeof(T) * 8>(*it).to_string();
    // Strings generated by std::bitset::to_string are read right to left.
    // Reversing to left to right.
    std::reverse(str.begin(), str.end());
    ss << str;
  }
  return ss.str();
}

// Converts a left-to-right input string of '0' and '1' to a buffer of |T|
// words.
template <typename T>
std::vector<T> StreamToBuffer(std::string str) {
  // The input string is left-to-right, the input argument of std::bitset needs
  // to right-to-left. Instead of reversing tokens, reverse the entire string
  // and iterate tokens from end to begin.
  std::reverse(str.begin(), str.end());
  const int word_size = static_cast<int>(sizeof(T) * 8);
  const int str_length = static_cast<int>(str.length());
  std::vector<T> buffer;
  buffer.reserve(NumBitsToNumWords<sizeof(T)>(str.length()));
  for (int index = str_length - word_size; index >= 0; index -= word_size) {
    buffer.push_back(static_cast<T>(
        std::bitset<sizeof(T) * 8>(str, index, word_size).to_ullong()));
  }
  const size_t suffix_length = str.length() % word_size;
  if (suffix_length != 0) {
    buffer.push_back(static_cast<T>(
        std::bitset<sizeof(T) * 8>(str, 0, suffix_length).to_ullong()));
  }
  return buffer;
}

// Adds '0' chars at the end of the string until the size is a multiple of N.
template <size_t N>
inline std::string PadToWord(std::string&& str) {
  const size_t tail_length = str.size() % N;
  if (tail_length != 0) str += std::string(N - tail_length, '0');
  return str;
}

// Adds '0' chars at the end of the string until the size is a multiple of N.
template <size_t N>
inline std::string PadToWord(const std::string& str) {
  return PadToWord<N>(std::string(str));
}

// Converts a left-to-right stream of bits to std::bitset.
template <size_t N>
inline std::bitset<N> StreamToBitset(std::string str) {
  std::reverse(str.begin(), str.end());
  return std::bitset<N>(str);
}

// Converts first |num_bits| of std::bitset to a left-to-right stream of bits.
template <size_t N>
inline std::string BitsetToStream(const std::bitset<N>& bits,
                                  size_t num_bits = N) {
  std::string str = bits.to_string().substr(N - num_bits);
  std::reverse(str.begin(), str.end());
  return str;
}<commit_msg>Fixes #1521: PadToWord() should use std::move() in && variant<commit_after>// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Contains utils for reading, writing and debug printing bit streams.

#ifndef LIBSPIRV_UTIL_BIT_STREAM_H_
#define LIBSPIRV_UTIL_BIT_STREAM_H_

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <functional>
#include <sstream>
#include <string>
#include <vector>

namespace spvutils {

// Returns rounded down log2(val). log2(0) is considered 0.
size_t Log2U64(uint64_t val);

// Terminology:
// Bits - usually used for a uint64 word, first bit is the lowest.
// Stream - std::string of '0' and '1', read left-to-right,
//          i.e. first bit is at the front and not at the end as in
//          std::bitset::to_string().
// Bitset - std::bitset corresponding to uint64 bits and to reverse(stream).

// Converts number of bits to a respective number of chunks of size N.
// For example NumBitsToNumWords<8> returns how many bytes are needed to store
// |num_bits|.
template <size_t N>
inline size_t NumBitsToNumWords(size_t num_bits) {
  return (num_bits + (N - 1)) / N;
}

// Returns value of the same type as |in|, where all but the first |num_bits|
// are set to zero.
template <typename T>
inline T GetLowerBits(T in, size_t num_bits) {
  return sizeof(T) * 8 == num_bits ? in : in & T((T(1) << num_bits) - T(1));
}

// Encodes signed integer as unsigned in zigzag order:
//  0 -> 0
// -1 -> 1
//  1 -> 2
// -2 -> 3
//  2 -> 4
// Motivation: -1 is 0xFF...FF what doesn't work very well with
// WriteVariableWidth which prefers to have as many 0 bits as possible.
inline uint64_t EncodeZigZag(int64_t val) { return (val << 1) ^ (val >> 63); }

// Decodes signed integer encoded with EncodeZigZag.
inline int64_t DecodeZigZag(uint64_t val) {
  if (val & 1) {
    // Negative.
    // 1 -> -1
    // 3 -> -2
    // 5 -> -3
    return -1 - (val >> 1);
  } else {
    // Non-negative.
    // 0 -> 0
    // 2 -> 1
    // 4 -> 2
    return val >> 1;
  }
}

// Encodes signed integer as unsigned. This is a generalized version of
// EncodeZigZag, designed to favor small positive numbers.
// Values are transformed in blocks of 2^|block_exponent|.
// If |block_exponent| is zero, then this degenerates into normal EncodeZigZag.
// Example when |block_exponent| is 1 (return value is the index):
// 0, 1, -1, -2, 2, 3, -3, -4, 4, 5, -5, -6, 6, 7, -7, -8
// Example when |block_exponent| is 2:
// 0, 1, 2, 3, -1, -2, -3, -4, 4, 5, 6, 7, -5, -6, -7, -8
inline uint64_t EncodeZigZag(int64_t val, size_t block_exponent) {
  assert(block_exponent < 64);
  const uint64_t uval = static_cast<uint64_t>(val >= 0 ? val : -val - 1);
  const uint64_t block_num =
      ((uval >> block_exponent) << 1) + (val >= 0 ? 0 : 1);
  const uint64_t pos = GetLowerBits(uval, block_exponent);
  return (block_num << block_exponent) + pos;
}

// Decodes signed integer encoded with EncodeZigZag. |block_exponent| must be
// the same.
inline int64_t DecodeZigZag(uint64_t val, size_t block_exponent) {
  assert(block_exponent < 64);
  const uint64_t block_num = val >> block_exponent;
  const uint64_t pos = GetLowerBits(val, block_exponent);
  if (block_num & 1) {
    // Negative.
    return -1LL - ((block_num >> 1) << block_exponent) - pos;
  } else {
    // Positive.
    return ((block_num >> 1) << block_exponent) + pos;
  }
}

// Converts |buffer| to a stream of '0' and '1'.
template <typename T>
std::string BufferToStream(const std::vector<T>& buffer) {
  std::stringstream ss;
  for (auto it = buffer.begin(); it != buffer.end(); ++it) {
    std::string str = std::bitset<sizeof(T) * 8>(*it).to_string();
    // Strings generated by std::bitset::to_string are read right to left.
    // Reversing to left to right.
    std::reverse(str.begin(), str.end());
    ss << str;
  }
  return ss.str();
}

// Converts a left-to-right input string of '0' and '1' to a buffer of |T|
// words.
template <typename T>
std::vector<T> StreamToBuffer(std::string str) {
  // The input string is left-to-right, the input argument of std::bitset needs
  // to right-to-left. Instead of reversing tokens, reverse the entire string
  // and iterate tokens from end to begin.
  std::reverse(str.begin(), str.end());
  const int word_size = static_cast<int>(sizeof(T) * 8);
  const int str_length = static_cast<int>(str.length());
  std::vector<T> buffer;
  buffer.reserve(NumBitsToNumWords<sizeof(T)>(str.length()));
  for (int index = str_length - word_size; index >= 0; index -= word_size) {
    buffer.push_back(static_cast<T>(
        std::bitset<sizeof(T) * 8>(str, index, word_size).to_ullong()));
  }
  const size_t suffix_length = str.length() % word_size;
  if (suffix_length != 0) {
    buffer.push_back(static_cast<T>(
        std::bitset<sizeof(T) * 8>(str, 0, suffix_length).to_ullong()));
  }
  return buffer;
}

// Adds '0' chars at the end of the string until the size is a multiple of N.
template <size_t N>
inline std::string PadToWord(std::string&& str) {
  const size_t tail_length = str.size() % N;
  if (tail_length != 0) str += std::string(N - tail_length, '0');
  return std::move(str);
}

// Adds '0' chars at the end of the string until the size is a multiple of N.
template <size_t N>
inline std::string PadToWord(const std::string& str) {
  return PadToWord<N>(std::string(str));
}

// Converts a left-to-right stream of bits to std::bitset.
template <size_t N>
inline std::bitset<N> StreamToBitset(std::string str) {
  std::reverse(str.begin(), str.end());
  return std::bitset<N>(str);
}

// Converts first |num_bits| of std::bitset to a left-to-right stream of bits.
template <size_t N>
inline std::string BitsetToStream(const std::bitset<N>& bits,
                                  size_t num_bits = N) {
  std::string str = bits.to_string().substr(N - num_bits);
  std::reverse(str.begin(), str.end());
  return str;
}
{'fraction_non_alphanumeric': 0.14156791964215648, 'fraction_numerical': 0.024170132621831594, 'mean_word_length': 3.3214649033570702, 'pattern_counts': {'":': 0, '<': 99, '<?xml version=': 0, '>': 123, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6167300', 'n_tokens_mistral': 4581, 'n_tokens_neox': 4367, 'n_words': 1495}