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.android.internal.telephony.uicc.asn1;
  
  import android.annotation.Nullable;
  
  import com.android.internal.telephony.uicc.IccUtils;
  
  import java.nio.charset.StandardCharsets;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  
  /**
   * This represents a primitive or constructed data defined by ASN.1. A constructed node can have
   * child nodes. A non-constructed node can have a value. This class is read-only. To build a node,
   * you can use the {@link #newBuilder(int)} method to get a {@link Builder} instance. This class is
   * not thread-safe.
   */
  public final class Asn1Node {
      private static final int INT_BYTES = Integer.SIZE / Byte.SIZE;
      private static final List<Asn1Node> EMPTY_NODE_LIST = Collections.emptyList();
  
      // Bytes for boolean values.
      private static final byte[] TRUE_BYTES = new byte[] {-1};
      private static final byte[] FALSE_BYTES = new byte[] {0};
  
      /**
       * This class is used to build an Asn1Node instance of a constructed tag. This class is not
       * thread-safe.
       */
      public static final class Builder {
          private final int mTag;
          private final List<Asn1Node> mChildren;
  
          private Builder(int tag) {
              if (!isConstructedTag(tag)) {
                  throw new IllegalArgumentException(
                          "Builder should be created for a constructed tag: " + tag);
              }
              mTag = tag;
              mChildren = new ArrayList<>();
          }
  
          /**
           * Adds a child from an existing node.
           *
           * @return This builder.
           * @throws IllegalArgumentException If the child is a non-existing node.
           */
          public Builder addChild(Asn1Node child) {
              mChildren.add(child);
              return this;
          }
  
          /**
           * Adds a child from another builder. The child will be built with the call to this method,
           * and any changes to the child builder after the call to this method doesn't have effect.
           *
           * @return This builder.
           */
          public Builder addChild(Builder child) {
              mChildren.add(child.build());
              return this;
          }
  
          /**
           * Adds children from bytes. This method calls {@link Asn1Decoder} to verify the {@code
           * encodedBytes} and adds all nodes parsed from it as children.
           *
           * @return This builder.
           * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
           */
          public Builder addChildren(byte[] encodedBytes) throws InvalidAsn1DataException {
              Asn1Decoder subDecoder = new Asn1Decoder(encodedBytes, 0, encodedBytes.length);
              while (subDecoder.hasNextNode()) {
                  mChildren.add(subDecoder.nextNode());
              }
              return this;
          }
  
          /**
           * Adds a child of non-constructed tag with an integer as the data.
           *
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsInteger(int tag, int value) {
              if (isConstructedTag(tag)) {
                  throw new IllegalStateException("Cannot set value of a constructed tag: " + tag);
              }
              byte[] dataBytes = IccUtils.signedIntToBytes(value);
              addChild(new Asn1Node(tag, dataBytes, 0, dataBytes.length));
              return this;
          }
  
          /**
           * Adds a child of non-constructed tag with a string as the data.
           *
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsString(int tag, String value) {
              if (isConstructedTag(tag)) {
                  throw new IllegalStateException("Cannot set value of a constructed tag: " + tag);
              }
              byte[] dataBytes = value.getBytes(StandardCharsets.UTF_8);
              addChild(new Asn1Node(tag, dataBytes, 0, dataBytes.length));
              return this;
          }
  
          /**
           * Adds a child of non-constructed tag with a byte array as the data.
           *
           * @param value The value will be owned by this node.
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsBytes(int tag, byte[] value) {
              if (isConstructedTag(tag)) {
                  throw new IllegalStateException("Cannot set value of a constructed tag: " + tag);
              }
              addChild(new Asn1Node(tag, value, 0, value.length));
              return this;
          }
  
          /**
           * Adds a child of non-constructed tag with a byte array as the data from a hex string.
           *
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsBytesFromHex(int tag, String hex) {
              return addChildAsBytes(tag, IccUtils.hexStringToBytes(hex));
          }
  
          /**
           * Adds a child of non-constructed tag with bits as the data.
           *
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsBits(int tag, int value) {
              if (isConstructedTag(tag)) {
                  throw new IllegalStateException("Cannot set value of a constructed tag: " + tag);
              }
              // Always allocate 5 bytes for simplicity.
              byte[] dataBytes = new byte[INT_BYTES + 1];
              // Puts the integer into the byte[1-4].
              value = Integer.reverse(value);
              int dataLength = 0;
              for (int i = 1; i < dataBytes.length; i++) {
                  dataBytes[i] = (byte) (value >> ((INT_BYTES - i) * Byte.SIZE));
                  if (dataBytes[i] != 0) {
                      dataLength = i;
                  }
              }
              dataLength++;
              // The first byte is the number of trailing zeros of the last byte.
              dataBytes[0] = IccUtils.countTrailingZeros(dataBytes[dataLength - 1]);
              addChild(new Asn1Node(tag, dataBytes, 0, dataLength));
              return this;
          }
  
          /**
           * Adds a child of non-constructed tag with a boolean as the data.
           *
           * @return This builder.
           * @throws IllegalStateException If the {@code tag} is not constructed..
           */
          public Builder addChildAsBoolean(int tag, boolean value) {
              if (isConstructedTag(tag)) {
                  throw new IllegalStateException("Cannot set value of a constructed tag: " + tag);
              }
              addChild(new Asn1Node(tag, value ? TRUE_BYTES : FALSE_BYTES, 0, 1));
              return this;
          }
  
          /** Builds the node. */
          public Asn1Node build() {
              return new Asn1Node(mTag, mChildren);
          }
      }
  
      private final int mTag;
      private final boolean mConstructed;
      // Do not use this field directly in the methods other than the constructor and encoding
      // methods (e.g., toBytes()), but always use getChildren() instead.
      private final List<Asn1Node> mChildren;
  
      // Byte array that actually holds the data. For a non-constructed node, this stores its actual
      // value. If the value is not set, this is null. For constructed node, this stores encoded data
      // of its children, which will be decoded on the first call to getChildren().
      private @Nullable byte[] mDataBytes;
      // Offset of the data in above byte array.
      private int mDataOffset;
      // Length of the data in above byte array. If it's a constructed node, this is always the total
      // length of all its children.
      private int mDataLength;
      // Length of the total bytes required to encode this node.
      private int mEncodedLength;
  
      /**
       * Creates a new ASN.1 data node builder with the given tag. The tag is an encoded tag including
       * the tag class, tag number, and constructed mask.
       */
      public static Builder newBuilder(int tag) {
          return new Builder(tag);
      }
  
      private static boolean isConstructedTag(int tag) {
          // Constructed mask is at the 6th bit.
          byte[] tagBytes = IccUtils.unsignedIntToBytes(tag);
          return (tagBytes[0] & 0x20) != 0;
      }
  
      private static int calculateEncodedBytesNumForLength(int length) {
          // Constructed mask is at the 6th bit.
          int len = 1;
          if (length > 127) {
              len += IccUtils.byteNumForUnsignedInt(length);
          }
          return len;
      }
  
      /**
       * Creates a node with given data bytes. If it is a constructed node, its children will be
       * parsed when they are visited.
       */
      Asn1Node(int tag, @Nullable byte[] src, int offset, int length) {
          mTag = tag;
          // Constructed mask is at the 6th bit.
          mConstructed = isConstructedTag(tag);
          mDataBytes = src;
          mDataOffset = offset;
          mDataLength = length;
          mChildren = mConstructed ? new ArrayList<Asn1Node>() : EMPTY_NODE_LIST;
          mEncodedLength =
                  IccUtils.byteNumForUnsignedInt(mTag)
                          + calculateEncodedBytesNumForLength(mDataLength)
                          + mDataLength;
      }
  
      /** Creates a constructed node with given children. */
      private Asn1Node(int tag, List<Asn1Node> children) {
          mTag = tag;
          mConstructed = true;
          mChildren = children;
  
          mDataLength = 0;
          int size = children.size();
          for (int i = 0; i < size; i++) {
              mDataLength += children.get(i).mEncodedLength;
          }
          mEncodedLength =
                  IccUtils.byteNumForUnsignedInt(mTag)
                          + calculateEncodedBytesNumForLength(mDataLength)
                          + mDataLength;
      }
  
      public int getTag() {
          return mTag;
      }
  
      public boolean isConstructed() {
          return mConstructed;
      }
  
      /**
       * Tests if a node has a child.
       *
       * @param tag The tag of an immediate child.
       * @param tags The tags of lineal descendant.
       */
      public boolean hasChild(int tag, int... tags) throws InvalidAsn1DataException {
          try {
              getChild(tag, tags);
          } catch (TagNotFoundException e) {
              return false;
          }
          return true;
      }
  
      /**
       * Gets the first child node having the given {@code tag} and {@code tags}.
       *
       * @param tag The tag of an immediate child.
       * @param tags The tags of lineal descendant.
       * @throws TagNotFoundException If the child cannot be found.
       */
      public Asn1Node getChild(int tag, int... tags)
              throws TagNotFoundException, InvalidAsn1DataException {
          if (!mConstructed) {
              throw new TagNotFoundException(tag);
          }
          int index = 0;
          Asn1Node node = this;
          while (node != null) {
              List<Asn1Node> children = node.getChildren();
              int size = children.size();
              Asn1Node foundChild = null;
              for (int i = 0; i < size; i++) {
                  Asn1Node child = children.get(i);
                  if (child.getTag() == tag) {
                      foundChild = child;
                      break;
                  }
              }
              node = foundChild;
              if (index >= tags.length) {
                  break;
              }
              tag = tags[index++];
          }
          if (node == null) {
              throw new TagNotFoundException(tag);
          }
          return node;
      }
  
      /**
       * Gets all child nodes which have the given {@code tag}.
       *
       * @return If this is primitive or no such children are found, an empty list will be returned.
       */
      public List<Asn1Node> getChildren(int tag)
              throws TagNotFoundException, InvalidAsn1DataException {
          if (!mConstructed) {
              return EMPTY_NODE_LIST;
          }
  
          List<Asn1Node> children = getChildren();
          if (children.isEmpty()) {
              return EMPTY_NODE_LIST;
          }
          List<Asn1Node> output = new ArrayList<>();
          int size = children.size();
          for (int i = 0; i < size; i++) {
              Asn1Node child = children.get(i);
              if (child.getTag() == tag) {
                  output.add(child);
              }
          }
          return output.isEmpty() ? EMPTY_NODE_LIST : output;
      }
  
      /**
       * Gets all child nodes of this node. If it's a constructed node having encoded data, it's
       * children will be decoded here.
       *
       * @return If this is primitive, an empty list will be returned. Do not modify the returned list
       *     directly.
       */
      public List<Asn1Node> getChildren() throws InvalidAsn1DataException {
          if (!mConstructed) {
              return EMPTY_NODE_LIST;
          }
  
          if (mDataBytes != null) {
              Asn1Decoder subDecoder = new Asn1Decoder(mDataBytes, mDataOffset, mDataLength);
              while (subDecoder.hasNextNode()) {
                  mChildren.add(subDecoder.nextNode());
              }
              mDataBytes = null;
              mDataOffset = 0;
          }
          return mChildren;
      }
  
      /** @return Whether this node has a value. False will be returned for a constructed node. */
      public boolean hasValue() {
          return !mConstructed && mDataBytes != null;
      }
  
      /**
       * @return The data as an integer. If the data length is larger than 4, only the first 4 bytes
       *     will be parsed.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public int asInteger() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          try {
              return IccUtils.bytesToInt(mDataBytes, mDataOffset, mDataLength);
          } catch (IllegalArgumentException | IndexOutOfBoundsException e) {
              throw new InvalidAsn1DataException(mTag, "Cannot parse data bytes.", e);
          }
      }
  
      /**
       * @return The data as a long variable which can be both positive and negative. If the data
       *     length is larger than 8, only the first 8 bytes will be parsed.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public long asRawLong() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          try {
              return IccUtils.bytesToRawLong(mDataBytes, mDataOffset, mDataLength);
          } catch (IllegalArgumentException | IndexOutOfBoundsException e) {
              throw new InvalidAsn1DataException(mTag, "Cannot parse data bytes.", e);
          }
      }
  
      /**
       * @return The data as a string in UTF-8 encoding.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public String asString() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          try {
              return new String(mDataBytes, mDataOffset, mDataLength, StandardCharsets.UTF_8);
          } catch (IndexOutOfBoundsException e) {
              throw new InvalidAsn1DataException(mTag, "Cannot parse data bytes.", e);
          }
      }
  
      /**
       * @return The data as a byte array.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public byte[] asBytes() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          byte[] output = new byte[mDataLength];
          try {
              System.arraycopy(mDataBytes, mDataOffset, output, 0, mDataLength);
          } catch (IndexOutOfBoundsException e) {
              throw new InvalidAsn1DataException(mTag, "Cannot parse data bytes.", e);
          }
          return output;
      }
  
      /**
       * Gets the data as an integer for BIT STRING. DER actually stores the bits in a reversed order.
       * The returned integer here has the order fixed (first bit is at the lowest position). This
       * method currently only support at most 32 bits which fit in an integer.
       *
       * @return The data as an integer. If this is constructed, a {@code null} will be returned.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public int asBits() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          int bits;
          try {
              bits = IccUtils.bytesToInt(mDataBytes, mDataOffset + 1, mDataLength - 1);
          } catch (IllegalArgumentException | IndexOutOfBoundsException e) {
              throw new InvalidAsn1DataException(mTag, "Cannot parse data bytes.", e);
          }
          for (int i = mDataLength - 1; i < INT_BYTES; i++) {
              bits <<= Byte.SIZE;
          }
          return Integer.reverse(bits);
      }
  
      /**
       * @return The data as a boolean.
       * @throws InvalidAsn1DataException If the data bytes cannot be parsed.
       */
      public boolean asBoolean() throws InvalidAsn1DataException {
          if (mConstructed) {
              throw new IllegalStateException("Cannot get value of a constructed node.");
          }
          if (mDataBytes == null) {
              throw new InvalidAsn1DataException(mTag, "Data bytes cannot be null.");
          }
          if (mDataLength != 1) {
              throw new InvalidAsn1DataException(
                      mTag, "Cannot parse data bytes as boolean: length=" + mDataLength);
          }
          if (mDataOffset < 0 || mDataOffset >= mDataBytes.length) {
              throw new InvalidAsn1DataException(
                      mTag,
                      "Cannot parse data bytes.",
                      new ArrayIndexOutOfBoundsException(mDataOffset));
          }
          // ASN.1 has "true" as 0xFF.
          if (mDataBytes[mDataOffset] == -1) {
              return Boolean.TRUE;
          } else if (mDataBytes[mDataOffset] == 0) {
              return Boolean.FALSE;
          }
          throw new InvalidAsn1DataException(
                  mTag, "Cannot parse data bytes as boolean: " + mDataBytes[mDataOffset]);
      }
  
      /** @return The number of required bytes for encoding this node in DER. */
      public int getEncodedLength() {
          return mEncodedLength;
      }
  
      /** @return The number of required bytes for encoding this node's data in DER. */
      public int getDataLength() {
          return mDataLength;
      }
  
      /**
       * Writes the DER encoded bytes of this node into a byte array. The number of written bytes is
       * {@link #getEncodedLength()}.
       *
       * @throws IndexOutOfBoundsException If the {@code dest} doesn't have enough space to write.
       */
      public void writeToBytes(byte[] dest, int offset) {
          if (offset < 0 || offset + mEncodedLength > dest.length) {
              throw new IndexOutOfBoundsException(
                      "Not enough space to write. Required bytes: " + mEncodedLength);
          }
          write(dest, offset);
      }
  
      /** Writes the DER encoded bytes of this node into a new byte array. */
      public byte[] toBytes() {
          byte[] dest = new byte[mEncodedLength];
          write(dest, 0);
          return dest;
      }
  
      /** Gets a hex string representing the DER encoded bytes of this node. */
      public String toHex() {
          return IccUtils.bytesToHexString(toBytes());
      }
  
      /** Gets header (tag + length) as hex string. */
      public String getHeadAsHex() {
          String headHex = IccUtils.bytesToHexString(IccUtils.unsignedIntToBytes(mTag));
          if (mDataLength <= 127) {
              headHex += IccUtils.byteToHex((byte) mDataLength);
          } else {
              byte[] lenBytes = IccUtils.unsignedIntToBytes(mDataLength);
              headHex += IccUtils.byteToHex((byte) (lenBytes.length | 0x80));
              headHex += IccUtils.bytesToHexString(lenBytes);
          }
          return headHex;
      }
  
      /** Returns the new offset where to write the next node data. */
      private int write(byte[] dest, int offset) {
          // Writes the tag.
          offset += IccUtils.unsignedIntToBytes(mTag, dest, offset);
          // Writes the length.
          if (mDataLength <= 127) {
              dest[offset++] = (byte) mDataLength;
          } else {
              // Bytes required for encoding the length
              int lenLen = IccUtils.unsignedIntToBytes(mDataLength, dest, ++offset);
              dest[offset - 1] = (byte) (lenLen | 0x80);
              offset += lenLen;
          }
          // Writes the data.
          if (mConstructed && mDataBytes == null) {
              int size = mChildren.size();
              for (int i = 0; i < size; i++) {
                  Asn1Node child = mChildren.get(i);
                  offset = child.write(dest, offset);
              }
          } else if (mDataBytes != null) {
              System.arraycopy(mDataBytes, mDataOffset, dest, offset, mDataLength);
              offset += mDataLength;
          }
          return offset;
      }
  }
  