content: /*
   * Copyright (C) 2016 The Android Open Source Project
   *
   * 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.
   */
  package com.google.android.exoplayer2.extractor.ogg;
  
  import android.util.Log;
  import com.google.android.exoplayer2.ParserException;
  import com.google.android.exoplayer2.util.ParsableByteArray;
  import java.util.Arrays;
  
  /**
   * Utility methods for parsing vorbis streams.
   */
  /* package */ final class VorbisUtil {
  
    private static final String TAG = "VorbisUtil";
  
    /**
     * Returns ilog(x), which is the index of the highest set bit in {@code x}.
     *
     * @see <a href="https://www.xiph.org/vorbis/doc/Vorbis_I_spec.html#x1-1190009.2.1">
     *     Vorbis spec</a>
     * @param x the value of which the ilog should be calculated.
     * @return ilog(x)
     */
    public static int iLog(int x) {
      int val = 0;
      while (x > 0) {
        val++;
        x >>>= 1;
      }
      return val;
    }
  
    /**
     * Reads a vorbis identification header from {@code headerData}.
     *
     * @see <a href="https://www.xiph.org/vorbis/doc/Vorbis_I_spec.html#x1-630004.2.2">Vorbis
     *     spec/Identification header</a>
     * @param headerData a {@link ParsableByteArray} wrapping the header data.
     * @return a {@link VorbisUtil.VorbisIdHeader} with meta data.
     * @throws ParserException thrown if invalid capture pattern is detected.
     */
    public static VorbisIdHeader readVorbisIdentificationHeader(ParsableByteArray headerData)
        throws ParserException {
  
      verifyVorbisHeaderCapturePattern(0x01, headerData, false);
  
      long version = headerData.readLittleEndianUnsignedInt();
      int channels = headerData.readUnsignedByte();
      long sampleRate = headerData.readLittleEndianUnsignedInt();
      int bitrateMax = headerData.readLittleEndianInt();
      int bitrateNominal = headerData.readLittleEndianInt();
      int bitrateMin = headerData.readLittleEndianInt();
  
      int blockSize = headerData.readUnsignedByte();
      int blockSize0 = (int) Math.pow(2, blockSize & 0x0F);
      int blockSize1 = (int) Math.pow(2, (blockSize & 0xF0) >> 4);
  
      boolean framingFlag = (headerData.readUnsignedByte() & 0x01) > 0;
      // raw data of vorbis setup header has to be passed to decoder as CSD buffer #1
      byte[] data = Arrays.copyOf(headerData.data, headerData.limit());
  
      return new VorbisIdHeader(version, channels, sampleRate, bitrateMax, bitrateNominal, bitrateMin,
          blockSize0, blockSize1, framingFlag, data);
    }
  
    /**
     * Reads a vorbis comment header.
     *
     * @see <a href="https://www.xiph.org/vorbis/doc/Vorbis_I_spec.html#x1-640004.2.3">
     *     Vorbis spec/Comment header</a>
     * @param headerData a {@link ParsableByteArray} wrapping the header data.
     * @return a {@link VorbisUtil.CommentHeader} with all the comments.
     * @throws ParserException thrown if invalid capture pattern is detected.
     */
    public static CommentHeader readVorbisCommentHeader(ParsableByteArray headerData)
        throws ParserException {
  
      verifyVorbisHeaderCapturePattern(0x03, headerData, false);
      int length = 7;
  
      int len = (int) headerData.readLittleEndianUnsignedInt();
      length += 4;
      String vendor = headerData.readString(len);
      length += vendor.length();
  
      long commentListLen = headerData.readLittleEndianUnsignedInt();
      String[] comments = new String[(int) commentListLen];
      length += 4;
      for (int i = 0; i < commentListLen; i++) {
        len = (int) headerData.readLittleEndianUnsignedInt();
        length += 4;
        comments[i] = headerData.readString(len);
        length += comments[i].length();
      }
      if ((headerData.readUnsignedByte() & 0x01) == 0) {
        throw new ParserException("framing bit expected to be set");
      }
      length += 1;
      return new CommentHeader(vendor, comments, length);
    }
  
    /**
     * Verifies whether the next bytes in {@code header} are a vorbis header of the given
     * {@code headerType}.
     *
     * @param headerType the type of the header expected.
     * @param header the alleged header bytes.
     * @param quiet if {@code true} no exceptions are thrown. Instead {@code false} is returned.
     * @return the number of bytes read.
     * @throws ParserException thrown if header type or capture pattern is not as expected.
     */
    public static boolean verifyVorbisHeaderCapturePattern(int headerType, ParsableByteArray header,
        boolean quiet)
        throws ParserException {
      if (header.bytesLeft() < 7) {
        if (quiet) {
          return false;
        } else {
          throw new ParserException("too short header: " + header.bytesLeft());
        }
      }
  
      if (header.readUnsignedByte() != headerType) {
        if (quiet) {
          return false;
        } else {
          throw new ParserException("expected header type " + Integer.toHexString(headerType));
        }
      }
  
      if (!(header.readUnsignedByte() == 'v'
          && header.readUnsignedByte() == 'o'
          && header.readUnsignedByte() == 'r'
          && header.readUnsignedByte() == 'b'
          && header.readUnsignedByte() == 'i'
          && header.readUnsignedByte() == 's')) {
        if (quiet) {
          return false;
        } else {
          throw new ParserException("expected characters 'vorbis'");
        }
      }
      return true;
    }
  
    /**
     * This method reads the modes which are located at the very end of the vorbis setup header.
     * That's why we need to partially decode or at least read the entire setup header to know
     * where to start reading the modes.
     *
     * @see <a href="https://www.xiph.org/vorbis/doc/Vorbis_I_spec.html#x1-650004.2.4">
     *     Vorbis spec/Setup header</a>
     * @param headerData a {@link ParsableByteArray} containing setup header data.
     * @param channels the number of channels.
     * @return an array of {@link Mode}s.
     * @throws ParserException thrown if bit stream is invalid.
     */
    public static Mode[] readVorbisModes(ParsableByteArray headerData, int channels)
        throws ParserException {
  
      verifyVorbisHeaderCapturePattern(0x05, headerData, false);
  
      int numberOfBooks = headerData.readUnsignedByte() + 1;
  
      VorbisBitArray bitArray  = new VorbisBitArray(headerData.data);
      bitArray.skipBits(headerData.getPosition() * 8);
  
      for (int i = 0; i < numberOfBooks; i++) {
        readBook(bitArray);
      }
  
      int timeCount = bitArray.readBits(6) + 1;
      for (int i = 0; i < timeCount; i++) {
        if (bitArray.readBits(16) != 0x00) {
          throw new ParserException("placeholder of time domain transforms not zeroed out");
        }
      }
      readFloors(bitArray);
      readResidues(bitArray);
      readMappings(channels, bitArray);
  
      Mode[] modes = readModes(bitArray);
      if (!bitArray.readBit()) {
        throw new ParserException("framing bit after modes not set as expected");
      }
      return modes;
    }
  
    private static Mode[] readModes(VorbisBitArray bitArray) {
      int modeCount = bitArray.readBits(6) + 1;
      Mode[] modes = new Mode[modeCount];
      for (int i = 0; i < modeCount; i++) {
        boolean blockFlag = bitArray.readBit();
        int windowType = bitArray.readBits(16);
        int transformType = bitArray.readBits(16);
        int mapping = bitArray.readBits(8);
        modes[i] = new Mode(blockFlag, windowType, transformType, mapping);
      }
      return modes;
    }
  
    private static void readMappings(int channels, VorbisBitArray bitArray)
        throws ParserException {
      int mappingsCount = bitArray.readBits(6) + 1;
      for (int i = 0; i < mappingsCount; i++) {
        int mappingType = bitArray.readBits(16);
        switch (mappingType) {
          case 0:
            int submaps;
            if (bitArray.readBit()) {
              submaps = bitArray.readBits(4) + 1;
            } else {
              submaps = 1;
            }
            int couplingSteps;
            if (bitArray.readBit()) {
              couplingSteps = bitArray.readBits(8) + 1;
              for (int j = 0; j < couplingSteps; j++) {
                bitArray.skipBits(iLog(channels - 1)); // magnitude
                bitArray.skipBits(iLog(channels - 1)); // angle
              }
            } /*else {
              couplingSteps = 0;
            }*/
            if (bitArray.readBits(2) != 0x00) {
              throw new ParserException("to reserved bits must be zero after mapping coupling steps");
            }
            if (submaps > 1) {
              for (int j = 0; j < channels; j++) {
                bitArray.skipBits(4); // mappingMux
              }
            }
            for (int j = 0; j < submaps; j++) {
              bitArray.skipBits(8); // discard
              bitArray.skipBits(8); // submapFloor
              bitArray.skipBits(8); // submapResidue
            }
            break;
          default:
            Log.e(TAG, "mapping type other than 0 not supported: " + mappingType);
        }
      }
    }
  
    private static void readResidues(VorbisBitArray bitArray) throws ParserException {
      int residueCount = bitArray.readBits(6) + 1;
      for (int i = 0; i < residueCount; i++) {
        int residueType = bitArray.readBits(16);
        if (residueType > 2) {
          throw new ParserException("residueType greater than 2 is not decodable");
        } else {
          bitArray.skipBits(24); // begin
          bitArray.skipBits(24); // end
          bitArray.skipBits(24); // partitionSize (add one)
          int classifications = bitArray.readBits(6) + 1;
          bitArray.skipBits(8); // classbook
          int[] cascade = new int[classifications];
          for (int j = 0; j < classifications; j++) {
            int highBits = 0;
            int lowBits = bitArray.readBits(3);
            if (bitArray.readBit()) {
              highBits = bitArray.readBits(5);
            }
            cascade[j] = highBits * 8 + lowBits;
          }
          for (int j = 0; j < classifications; j++) {
            for (int k = 0; k < 8; k++) {
              if ((cascade[j] & (0x01 << k)) != 0) {
                bitArray.skipBits(8); // discard
              }
            }
          }
        }
      }
    }
  
    private static void readFloors(VorbisBitArray bitArray) throws ParserException {
      int floorCount = bitArray.readBits(6) + 1;
      for (int i = 0; i < floorCount; i++) {
        int floorType = bitArray.readBits(16);
        switch (floorType) {
          case 0:
            bitArray.skipBits(8); //order
            bitArray.skipBits(16); // rate
            bitArray.skipBits(16); // barkMapSize
            bitArray.skipBits(6); // amplitudeBits
            bitArray.skipBits(8); // amplitudeOffset
            int floorNumberOfBooks = bitArray.readBits(4) + 1;
            for (int j = 0; j < floorNumberOfBooks; j++) {
              bitArray.skipBits(8);
            }
            break;
          case 1:
            int partitions = bitArray.readBits(5);
            int maximumClass = -1;
            int[] partitionClassList = new int[partitions];
            for (int j = 0; j < partitions; j++) {
              partitionClassList[j] = bitArray.readBits(4);
              if (partitionClassList[j] > maximumClass) {
                maximumClass = partitionClassList[j];
              }
            }
            int[] classDimensions = new int[maximumClass + 1];
            for (int j = 0; j < classDimensions.length; j++) {
              classDimensions[j] = bitArray.readBits(3) + 1;
              int classSubclasses = bitArray.readBits(2);
              if (classSubclasses > 0) {
                bitArray.skipBits(8); // classMasterbooks
              }
              for (int k = 0; k < (1 << classSubclasses); k++) {
                bitArray.skipBits(8); // subclassBook (subtract 1)
              }
            }
            bitArray.skipBits(2); // multiplier (add one)
            int rangeBits = bitArray.readBits(4);
            int count = 0;
            for (int j = 0, k = 0; j < partitions; j++) {
              int idx = partitionClassList[j];
              count += classDimensions[idx];
              for (; k < count; k++) {
                bitArray.skipBits(rangeBits); // floorValue
              }
            }
            break;
          default:
            throw new ParserException("floor type greater than 1 not decodable: " + floorType);
        }
      }
    }
  
    private static CodeBook readBook(VorbisBitArray bitArray) throws ParserException {
      if (bitArray.readBits(24) != 0x564342) {
        throw new ParserException("expected code book to start with [0x56, 0x43, 0x42] at "
            + bitArray.getPosition());
      }
      int dimensions = bitArray.readBits(16);
      int entries = bitArray.readBits(24);
      long[] lengthMap = new long[entries];
  
      boolean isOrdered = bitArray.readBit();
      if (!isOrdered) {
        boolean isSparse = bitArray.readBit();
        for (int i = 0; i < lengthMap.length; i++) {
          if (isSparse) {
            if (bitArray.readBit()) {
              lengthMap[i] = bitArray.readBits(5) + 1;
            } else { // entry unused
              lengthMap[i] = 0;
            }
          } else { // not sparse
            lengthMap[i] = bitArray.readBits(5) + 1;
          }
        }
      } else {
        int length = bitArray.readBits(5) + 1;
        for (int i = 0; i < lengthMap.length;) {
          int num = bitArray.readBits(iLog(entries - i));
          for (int j = 0; j < num && i < lengthMap.length; i++, j++) {
            lengthMap[i] = length;
          }
          length++;
        }
      }
  
      int lookupType = bitArray.readBits(4);
      if (lookupType > 2) {
        throw new ParserException("lookup type greater than 2 not decodable: " + lookupType);
      } else if (lookupType == 1 || lookupType == 2) {
        bitArray.skipBits(32); // minimumValue
        bitArray.skipBits(32); // deltaValue
        int valueBits = bitArray.readBits(4) + 1;
        bitArray.skipBits(1); // sequenceP
        long lookupValuesCount;
        if (lookupType == 1) {
          if (dimensions != 0) {
            lookupValuesCount = mapType1QuantValues(entries, dimensions);
          } else {
            lookupValuesCount = 0;
          }
        } else {
          lookupValuesCount = entries * dimensions;
        }
        // discard (no decoding required yet)
        bitArray.skipBits((int) (lookupValuesCount * valueBits));
      }
      return new CodeBook(dimensions, entries, lengthMap, lookupType, isOrdered);
    }
  
    /**
     * @see <a href="http://svn.xiph.org/trunk/vorbis/lib/sharedbook.c">_book_maptype1_quantvals</a>
     */
    private static long mapType1QuantValues(long entries, long dimension) {
      return (long) Math.floor(Math.pow(entries, 1.d / dimension));
    }
  
    public static final class CodeBook {
  
      public final int dimensions;
      public final int entries;
      public final long[] lengthMap;
      public final int lookupType;
      public final boolean isOrdered;
  
      public CodeBook(int dimensions, int entries, long[] lengthMap, int lookupType,
          boolean isOrdered) {
        this.dimensions = dimensions;
        this.entries = entries;
        this.lengthMap = lengthMap;
        this.lookupType = lookupType;
        this.isOrdered = isOrdered;
      }
  
    }
  
    public static final class CommentHeader {
  
      public final String vendor;
      public final String[] comments;
      public final int length;
  
      public CommentHeader(String vendor, String[] comments, int length) {
        this.vendor = vendor;
        this.comments = comments;
        this.length = length;
      }
  
    }
  
    public static final class VorbisIdHeader {
  
      public final long version;
      public final int channels;
      public final long sampleRate;
      public final int bitrateMax;
      public final int bitrateNominal;
      public final int bitrateMin;
      public final int blockSize0;
      public final int blockSize1;
      public final boolean framingFlag;
      public final byte[] data;
  
      public VorbisIdHeader(long version, int channels, long sampleRate, int bitrateMax,
          int bitrateNominal, int bitrateMin, int blockSize0, int blockSize1, boolean framingFlag,
          byte[] data) {
        this.version = version;
        this.channels = channels;
        this.sampleRate = sampleRate;
        this.bitrateMax = bitrateMax;
        this.bitrateNominal = bitrateNominal;
        this.bitrateMin = bitrateMin;
        this.blockSize0 = blockSize0;
        this.blockSize1 = blockSize1;
        this.framingFlag = framingFlag;
        this.data = data;
      }
  
      public int getApproximateBitrate() {
        return bitrateNominal == 0 ? (bitrateMin + bitrateMax) / 2 : bitrateNominal;
      }
  
    }
  
    public static final class Mode {
  
      public final boolean blockFlag;
      public final int windowType;
      public final int transformType;
      public final int mapping;
  
      public Mode(boolean blockFlag, int windowType, int transformType, int mapping) {
        this.blockFlag = blockFlag;
        this.windowType = windowType;
        this.transformType = transformType;
        this.mapping = mapping;
      }
  
    }
  
  }
  