neiam /gitgud

defmodule GitGud.Packages.Formats.Fdroid.Arsc do
  @moduledoc """
  Reads `resources.arsc` — enough of it to turn a resource id into the
  file it names, or the string it holds.

  This is the third binary format in the F-Droid adapter, after the
  manifest and the signing block, and for a while the adapter did
  without it: `android:icon` compiles to a bare resource id, and
  guessing `res/mipmap-xxxhdpi/ic_launcher.png` covers a debug build.

  It does not survive a release build. R8's resource shrinking rewrites
  every resource path, so this forge's own app ships `res/0Z.png` and
  `res/2K.9.png` and no `mipmap` directory at all. The names live only
  in here, which makes this the only way to answer "which of these 72
  PNGs is the launcher icon".

  ## Shape

  A table is a header, a global string pool holding every string value
  and file path, and one package per id (0x7f for an app's own
  resources, 0x01 for android's framework). A package carries two more
  pools — type names, key names — then, per type, a `ResTable_type`
  chunk for each configuration: one for xxhdpi, one for xxxhdpi, one
  for anydpi-v26, and so on. The same resource id therefore has several
  values, and picking between them is the caller's problem, which is
  why `file_paths/2` returns them ranked rather than picking one.

  A resource id is `0xPPTTEEEE`: package, type, entry index.

  ## Ranking

  Highest density first, and any `.xml` last. An adaptive icon lives in
  `mipmap-anydpi-v26` as XML that references two more drawables; it is
  the *best* icon on a phone and useless to a repository index, which
  needs an image it can serve. The PNG next to it is what F-Droid can
  show.

  ## Trust

  An APK is attacker-supplied. Every offset read out of the file is
  bounds-checked against the chunk it came from, no length is trusted,
  and a malformed table returns `{:error, _}` rather than raising —
  the same posture as `Manifest`.
  """

  import Bitwise

  # Chunk types, from ResourceTypes.h.
  @res_string_pool 0x0001
  @res_table 0x0002
  @res_table_package 0x0200
  @res_table_type 0x0201

  # String pool flags.
  @utf8_flag 0x100

  # ResTable_type flags.
  @flag_sparse 0x01
  @flag_offset16 0x02

  # ResTable_entry flags.
  @entry_complex 0x0001

  # Typed-value data types.
  @type_string 0x03

  # Densities that aren't measurements: "any" is the adaptive-icon
  # bucket and "none" means don't scale. Both sort below every real
  # density rather than above it, which is what taking them at face
  # value (0xFFFE) would do.
  @density_any 0xFFFE
  @density_none 0xFFFF

  # 64 MB of resources is not a table this needs to read.
  @max_size 64 * 1024 * 1024

  @typedoc "Parsed table: the global value pool plus each package's entries."
  @type t :: %{
          strings: tuple(),
          # %{resource id => [{density, value}]}
          entries: %{non_neg_integer() => [{non_neg_integer(), term()}]}
        }

  @doc """
  Parse `resources.arsc`.

  Returns `{:ok, table}` or `{:error, {status, message}}` shaped for the
  registry controller.
  """
  @spec parse(binary()) :: {:ok, t()} | {:error, {integer(), String.t()}}
  def parse(data) when is_binary(data) and byte_size(data) > @max_size,
    do: {:error, {422, "resources.arsc is implausibly large"}}

  def parse(<<@res_table::little-16, header_size::little-16, size::little-32, _::binary>> = data)
      when header_size >= 12 do
    cond do
      size > byte_size(data) ->
        {:error, {422, "resources.arsc is truncated"}}

      header_size > byte_size(data) ->
        {:error, {422, "resources.arsc header overruns the file"}}

      true ->
        body = binary_part(data, header_size, size - header_size)

        with {:ok, chunks} <- chunks(body, []),
             {:ok, strings} <- global_pool(chunks) do
          entries =
            chunks
            |> Enum.filter(fn {type, _, _} -> type == @res_table_package end)
            |> Enum.reduce(%{}, &package_entries/2)

          {:ok, %{strings: strings, entries: entries}}
        end
    end
  end

  def parse(_), do: {:error, {422, "not a resources.arsc"}}

  @doc """
  Every file path resource `id` resolves to, best first.

  Empty for an id that isn't a file reference, isn't in the table, or
  is a complex value (a style, an array) rather than a single one.
  """
  @spec file_paths(t(), non_neg_integer()) :: [String.t()]
  def file_paths(%{entries: entries} = table, id) when is_integer(id) do
    entries
    |> Map.get(id, [])
    |> Enum.flat_map(fn {density, value} ->
      case resolve_string(table, value) do
        nil -> []
        path -> [{density, path}]
      end
    end)
    |> Enum.sort_by(fn {density, path} -> {xml_rank(path), -rank_density(density)} end)
    |> Enum.map(&elem(&1, 1))
    |> Enum.uniq()
  end

  def file_paths(_, _), do: []

  @doc """
  The string resource `id` holds, or nil.

  Prefers the default configuration, which for a label is the
  untranslated one — the index has a single name field and the
  publisher's own language is the honest thing to put in it.
  """
  @spec string(t(), non_neg_integer()) :: String.t() | nil
  def string(%{entries: entries} = table, id) when is_integer(id) do
    entries
    |> Map.get(id, [])
    |> Enum.sort_by(fn {density, _} -> rank_density(density) end)
    |> Enum.find_value(fn {_, value} -> resolve_string(table, value) end)
  end

  def string(_, _), do: nil

  # ── values ───────────────────────────────────────────────────────────

  defp resolve_string(%{strings: strings}, {:string, index}), do: pool_at(strings, index)
  defp resolve_string(_table, _other), do: nil

  # `.xml` sorts after everything: it is a real value for an adaptive
  # icon and an unservable one for an index.
  defp xml_rank(path), do: if(String.ends_with?(path, ".xml"), do: 1, else: 0)

  defp rank_density(density) when density in [@density_any, @density_none], do: 0
  defp rank_density(density), do: density

  # ── chunk walking ────────────────────────────────────────────────────

  defp chunks(<<>>, acc), do: {:ok, Enum.reverse(acc)}

  defp chunks(
         <<type::little-16, header_size::little-16, size::little-32, _::binary>> = data,
         acc
       )
       when size >= 8 and header_size >= 8 and header_size <= size do
    if size > byte_size(data) do
      {:ok, Enum.reverse(acc)}
    else
      chunk = binary_part(data, 0, size)
      rest = binary_part(data, size, byte_size(data) - size)
      chunks(rest, [{type, header_size, chunk} | acc])
    end
  end

  defp chunks(_trailing, acc), do: {:ok, Enum.reverse(acc)}

  defp global_pool(chunks) do
    case Enum.find(chunks, fn {type, _, _} -> type == @res_string_pool end) do
      {_, header_size, chunk} -> parse_string_pool(chunk, header_size)
      nil -> {:error, {422, "resources.arsc has no string pool"}}
    end
  end

  # ── packages ─────────────────────────────────────────────────────────

  defp package_entries({_, header_size, chunk}, acc) do
    case chunk do
      <<_::binary-size(8), id::little-32, _rest::binary>> when header_size <= byte_size(chunk) ->
        package_id = band(id, 0xFF)
        body = binary_part(chunk, header_size, byte_size(chunk) - header_size)

        case chunks(body, []) do
          {:ok, inner} ->
            inner
            |> Enum.filter(fn {type, _, _} -> type == @res_table_type end)
            |> Enum.reduce(acc, &type_entries(&1, &2, package_id))

          _ ->
            acc
        end

      _ ->
        acc
    end
  end

  # One `ResTable_type` is one configuration's worth of one type: every
  # mipmap at xxhdpi, say. Entries are addressed by an offset table
  # whose encoding depends on the chunk's flags.
  defp type_entries({_, header_size, chunk}, acc, package_id) do
    case chunk do
      <<_::binary-size(8), type_id, flags, _reserved::little-16, entry_count::little-32,
        entries_start::little-32, config::binary>>
      when type_id > 0 and header_size <= byte_size(chunk) and
             entries_start <= byte_size(chunk) ->
        density = config_density(config)
        table_size = byte_size(chunk) - entries_start

        if table_size < 0 or entry_count > table_size do
          acc
        else
          data = binary_part(chunk, entries_start, table_size)

          id_base = bsl(package_id, 24) ||| bsl(type_id, 16)

          offsets(chunk, header_size, entry_count, flags)
          |> Enum.reduce(acc, &add_entry(&1, &2, data, id_base, density))
        end

      _ ->
        acc
    end
  end

  defp add_entry({index, offset}, acc, data, id_base, density) do
    case entry_value(data, offset) do
      {:ok, value} ->
        id = id_base ||| index
        Map.update(acc, id, [{density, value}], &[{density, value} | &1])

      :none ->
        acc
    end
  end

  # `{entry index, offset into the entry data}` for each present entry.
  # A 0xFFFFFFFF offset means "not defined in this configuration",
  # which is most of them in most configurations.
  defp offsets(chunk, header_size, count, flags) do
    cond do
      band(flags, @flag_sparse) != 0 ->
        read_offsets(chunk, header_size, count, 4, fn <<index::little-16, offset::little-16>> ->
          {index, offset * 4}
        end)

      band(flags, @flag_offset16) != 0 ->
        read_offsets(chunk, header_size, count, 2, fn <<offset::little-16>> ->
          {:sequential, if(offset == 0xFFFF, do: :absent, else: offset * 4)}
        end)
        |> sequential()

      true ->
        read_offsets(chunk, header_size, count, 4, fn <<offset::little-32>> ->
          {:sequential, if(offset == 0xFFFFFFFF, do: :absent, else: offset)}
        end)
        |> sequential()
    end
  end

  defp read_offsets(chunk, header_size, count, width, decode) do
    need = count * width

    if header_size + need > byte_size(chunk) do
      []
    else
      chunk
      |> binary_part(header_size, need)
      |> chunk_every_binary(width)
      |> Enum.map(decode)
    end
  end

  # The dense encodings list one slot per entry index, in order; the
  # sparse one carries its own indices and needs no numbering.
  defp sequential(decoded) do
    decoded
    |> Enum.with_index()
    |> Enum.flat_map(fn
      {{:sequential, :absent}, _index} -> []
      {{:sequential, offset}, index} -> [{index, offset}]
      {other, _index} -> [other]
    end)
  end

  defp chunk_every_binary(<<>>, _width), do: []

  defp chunk_every_binary(data, width) when byte_size(data) >= width do
    [
      binary_part(data, 0, width)
      | chunk_every_binary(binary_part(data, width, byte_size(data) - width), width)
    ]
  end

  defp chunk_every_binary(_data, _width), do: []

  # ResTable_entry, then the Res_value that follows it. Complex entries
  # (bags: styles, arrays, adaptive-icon *definitions*) carry a map
  # instead of a value and are not what a file reference looks like.
  defp entry_value(data, offset) when is_integer(offset) and offset >= 0 do
    with true <- offset + 8 <= byte_size(data),
         <<entry_size::little-16, entry_flags::little-16, _key::little-32, rest::binary>> <-
           binary_part(data, offset, byte_size(data) - offset),
         false <- band(entry_flags, @entry_complex) != 0,
         true <- entry_size >= 8,
         value_offset = entry_size - 8,
         <<_::binary-size(^value_offset), _size::little-16, _res0, data_type, value::little-32,
           _::binary>> <- rest do
      case data_type do
        @type_string -> {:ok, {:string, value}}
        _ -> :none
      end
    else
      _ -> :none
    end
  end

  defp entry_value(_data, _offset), do: :none

  # ResTable_config: size, imsi, locale, then screenType — whose third
  # field is the density. Anything shorter than that simply has none.
  defp config_density(
         <<_size::little-32, _imsi::binary-size(4), _locale::binary-size(4), _orientation,
           _touchscreen, density::little-16, _::binary>>
       ),
       do: density

  defp config_density(_), do: 0

  # ── string pool ──────────────────────────────────────────────────────

  defp parse_string_pool(chunk, header_size) do
    case chunk do
      <<_::binary-size(8), count::little-32, _styles::little-32, flags::little-32,
        strings_start::little-32, _styles_start::little-32, _::binary>> ->
        utf8? = band(flags, @utf8_flag) != 0

        with {:ok, offsets} <- pool_offsets(chunk, header_size, count) do
          data_len = byte_size(chunk) - strings_start

          if strings_start > byte_size(chunk) or data_len < 0 do
            {:error, {422, "string pool points outside its chunk"}}
          else
            data = binary_part(chunk, strings_start, data_len)

            strings =
              offsets
              |> Enum.map(&read_string(data, &1, utf8?))
              |> List.to_tuple()

            {:ok, strings}
          end
        end

      _ ->
        {:error, {422, "malformed string pool header"}}
    end
  end

  defp pool_offsets(chunk, header_size, count) do
    need = count * 4

    if header_size + need > byte_size(chunk) do
      {:error, {422, "string pool offset table is truncated"}}
    else
      {:ok, for(<<off::little-32 <- binary_part(chunk, header_size, need)>>, do: off)}
    end
  end

  defp read_string(data, offset, _utf8?) when offset >= byte_size(data), do: ""

  defp read_string(data, offset, true) do
    rest = binary_part(data, offset, byte_size(data) - offset)

    with {_utf16_len, rest} <- utf8_len(rest),
         {byte_len, rest} <- utf8_len(rest),
         true <- byte_len <= byte_size(rest) do
      binary_part(rest, 0, byte_len)
    else
      _ -> ""
    end
  end

  defp read_string(data, offset, false) do
    rest = binary_part(data, offset, byte_size(data) - offset)

    case rest do
      <<len::little-16, body::binary>> ->
        # High bit set means a two-word length; the low word follows.
        {len, body} =
          if band(len, 0x8000) != 0 do
            <<low::little-16, body::binary>> = body
            {bor(bsl(band(len, 0x7FFF), 16), low), body}
          else
            {len, body}
          end

        bytes = len * 2

        if bytes <= byte_size(body) do
          body |> binary_part(0, bytes) |> utf16_to_utf8()
        else
          ""
        end

      _ ->
        ""
    end
  end

  defp utf8_len(<<high, rest::binary>>) when band(high, 0x80) != 0 do
    case rest do
      <<low, rest::binary>> -> {bor(bsl(band(high, 0x7F), 8), low), rest}
      _ -> :error
    end
  end

  defp utf8_len(<<len, rest::binary>>), do: {len, rest}
  defp utf8_len(_), do: :error

  defp utf16_to_utf8(bytes) do
    case :unicode.characters_to_binary(bytes, {:utf16, :little}, :utf8) do
      converted when is_binary(converted) -> converted
      _ -> ""
    end
  end

  defp pool_at(pool, index) when is_integer(index) and index >= 0 and index < tuple_size(pool),
    do: elem(pool, index)

  defp pool_at(_pool, _index), do: nil
end