components/qr_code_generator/qr_code_generator.h

// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef COMPONENTS_QR_CODE_GENERATOR_QR_CODE_GENERATOR_H_
#define COMPONENTS_QR_CODE_GENERATOR_QR_CODE_GENERATOR_H_

#include <stddef.h>
#include <stdint.h>

#include <vector>

#include "base/containers/span.h"
#include "base/gtest_prod_util.h"
#include "base/memory/raw_ptr.h"
#include "third_party/abseil-cpp/absl/types/optional.h"

struct QRVersionInfo;

// QRCodeGenerator generates class M QR codes of various versions.
// References in the following comments refer to ISO 18004 (3rd edition).
// Supports versions up to 26 by adding constants.
class QRCodeGenerator {
 public:
  // Contains output data for Generate().
  // The default state contains no data.
  struct GeneratedCode {
   public:
    GeneratedCode();
    GeneratedCode(GeneratedCode&&);

    GeneratedCode(const GeneratedCode&) = delete;
    GeneratedCode& operator=(const GeneratedCode&) = delete;

    ~GeneratedCode();

    // Pixel data; pointer to an array of bytes, where the least-significant
    // bit of each byte is set if that tile should be "black".
    // Clients should ensure four modules of padding when rendering the code.
    // On error, will not be populated, and will evaluate to false.
    base::span<uint8_t> data;

    // Width and height (which are equal) of the generated data, in tiles.
    int qr_size = 0;
  };

  // Static parameters for V5 QR codes.
  // These exist while migrating clients to dynamic sizes.
  struct V5 {
    static constexpr int kSize = 37;
    static constexpr int kTotalSize = kSize * kSize;
    static constexpr size_t kNumSegments = 2;
    static constexpr size_t kSegmentDataBytes = 43;
    static constexpr size_t kDataBytes = kSegmentDataBytes * kNumSegments;
    static constexpr size_t kInputBytes = kDataBytes - 2;
  };

  // VersionClass enumerates the two types of QR code supported: small and
  // large. These differ in the size of the lengths used.
  enum class VersionClass {
    SMALL,
    LARGE,
    // Micro QR codes and versions >= 27 would be their own class but are not
    // supported.
  };

  // SegmentType enumerates the different data segments that can be in a QR
  // code. See section 7.3.
  enum class SegmentType {
    DIGIT = 1,
    ALPHANUM = 2,
    BINARY = 3,
    // ECI and Kanji segments are not supported.
  };

  // A Segment is a run of input bytes encoded as a given segment type.
  struct Segment {
    SegmentType type;
    size_t length;
  };

  QRCodeGenerator();
  ~QRCodeGenerator();

  // Generates a QR code containing the given data.
  // The generator will attempt to choose a version that fits the data and which
  // is >= |min_version|, if given. The returned span's length is
  // input-dependent and not known at compile-time. The optional |mask| argument
  // specifies the QR mask value to use (from 0 to 7). If not specified, the
  // optimal mask is calculated per the algorithm specified in the QR standard.
  absl::optional<GeneratedCode> Generate(
      base::span<const uint8_t> in,
      absl::optional<int> min_version = absl::nullopt,
      absl::optional<uint8_t> mask = absl::nullopt);

 private:
  FRIEND_TEST_ALL_PREFIXES(QRCodeGenerator, Segmentation);
  FRIEND_TEST_ALL_PREFIXES(QRCodeGenerator, SegmentationValid);

  // PutFinder paints a finder symbol at the given coordinates.
  void PutFinder(int x, int y);

  // PutAlignment paints an alignment symbol centered at the given coordinates.
  void PutAlignment(int x, int y);

  // PutVerticalTiming paints the vertical timing signal.
  void PutVerticalTiming(int x);

  // PutVerticalTiming paints the horizontal timing signal.
  void PutHorizontalTiming(int y);

  // PutFormatBits paints the 15-bit, pre-encoded format metadata. See page 56
  // for the location of the format bits.
  void PutFormatBits(const uint16_t format);

  // PutVersionBlocks writes the two blocks of version information for QR
  // versions seven and above.
  void PutVersionBlocks(const uint32_t encoded_version);

  // PutBits writes the given data into the QR code in correct order, avoiding
  // structural elements that must have already been painted. See section 7.7.3
  // about the placement algorithm.
  void PutBits(const uint8_t* data,
               size_t data_len,
               uint8_t (*mask_func)(int, int));

  // at returns a reference to the given element of |d_|.
  uint8_t& at(int x, int y);

  // fillAt sets the |len| elements at (x, y) to |value|.
  void fillAt(int x, int y, size_t len, uint8_t value);

  // copyTo copies |len| elements from |data| to the elements at (x, y).
  void copyTo(int x, int y, const uint8_t* data, size_t len);

  // clipped returns a reference to the given element of |d_|, or to
  // |clip_dump_| if the coordinates are out of bounds.
  uint8_t& clipped(int x, int y);

  // GF28Mul returns the product of |a| and |b| (which must be field elements,
  // i.e. < 256) in the field GF(2^8) mod x^8 + x^4 + x^3 + x^2 + 1.
  static uint8_t GF28Mul(uint16_t a, uint16_t b);

  // AddErrorCorrection writes the Reed-Solomon expanded version of |in| to
  // |out|.
  // |out| should have length block_bytes for the code's version.
  // |in| should have length block_data_bytes for the code's version.
  // |block_bytes| and |block_ec_bytes| must be provided for the current
  // version/level/group.
  void AddErrorCorrection(base::span<uint8_t> out,
                          base::span<const uint8_t> in,
                          size_t block_bytes,
                          size_t block_ec_bytes);

  // CountPenaltyPoints sums the penalty points for the current, fully drawn,
  // code. See table 11.
  unsigned CountPenaltyPoints() const;

  // ClassifyByte returns the smallest |SegmentType| that can encode |byte|.
  static SegmentType ClassifyByte(uint8_t byte);

  // IsValidSegmentation returns true if |segments| precisely covers |input|
  // with segments that can encode the corresponding byte of |input|.
  static bool IsValidSegmentation(const std::vector<Segment>& segments,
                                  base::span<const uint8_t> input);

  // NoSuperfluousSegments returns true if no consecutive segments in |segments|
  // have the same type.
  static bool NoSuperfluousSegments(const std::vector<Segment>& segments);

  // InitialSegmentation returns a segmentation of |input| that puts each
  // byte into the smallest |SegmentType| that can encode it while merging
  // consecutive segments of the same type.
  static std::vector<Segment> InitialSegmentation(
      base::span<const uint8_t> input);

  // MergeSegments replaces the segments indexed by |start| and |end|
  // (inclusive) with |replacement|.
  static size_t MergeSegments(std::vector<Segment>* segments,
                              size_t start,
                              size_t end,
                              Segment replacement);

  // MaybeMerge merges the segments indexed by |start| and |end| (inclusive)
  // with a single segment of type |merged_type|, if that merge would take fewer
  // bits.
  static size_t MaybeMerge(VersionClass vclass,
                           std::vector<Segment>* segments,
                           size_t start,
                           size_t end,
                           SegmentType merged_type);

  // SegmentDigitAlphaSpan updates the segments indexed by |start| and |end|
  // (inclusive) to be a fairly optimal segmentation. The indicated segments
  // must all be |DIGIT| or |ALPHANUM| segments.
  static size_t SegmentDigitAlphaSpan(VersionClass vclass,
                                      std::vector<Segment>* segments,
                                      size_t start,
                                      size_t end);

  // SegmentInput returns a fairly optimal segmentation of |input|.
  static std::vector<Segment> SegmentInput(VersionClass vclass,
                                           base::span<const uint8_t> input);

  // Parameters for the currently-selected version of the QR code.
  // Generate() will pick a version that can contain enough data.
  // Unowned; nullptr until initialized in Generate().
  raw_ptr<const QRVersionInfo> version_info_ = nullptr;

  // d_ represents a QR code with one byte per pixel. Each byte is one pixel.
  // The LSB is set if the pixel is "black". The second bit is set if the pixel
  // is part of the structure of the QR code, i.e. finder or alignment symbols,
  // timing patterns, or format data.
  // Initialized and possibly reinitialized in Generate().
  std::vector<uint8_t> d_;

  // clip_dump_ is the target of paints that would otherwise fall outside of the
  // QR code.
  uint8_t clip_dump_;
};

#endif  // COMPONENTS_QR_CODE_GENERATOR_QR_CODE_GENERATOR_H_