/* -*- mode: C; c-file-style: "gnu" -*- */

/* decode-gcov.c gcov decoder program

 *

 * Portion Copyright © 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

 * Copyright (C) 2003  Red Hat Inc.

 *

 * Partially derived from gcov,

 * Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998,

 * 1999, 2000, 2001, 2002 Free Software Foundation, Inc.

 *

 * This file is NOT licensed under the Academic Free License

 * as it is largely derived from gcov.c and gcov-io.h in the

 * gcc source code.

 * 

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 */

#define DBUS_COMPILATION /* cheat */

#ifndef __SYMBIAN32__

#include <dbus/dbus-list.h>

#include <dbus/dbus-string.h>

#include <dbus/dbus-sysdeps.h>

#include <dbus/dbus-hash.h>

#else

#include "dbus-list.h"

#include "dbus-string.h"

#include "dbus-sysdeps.h"

#include "dbus-hash.h"

#endif

#undef DBUS_COMPILATION

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#ifdef SYMBIAN

#define DBUS_HAVE_INT64 1

#endif

#ifndef DBUS_HAVE_INT64

#error "gcov support can't be built without 64-bit integer support"

#endif

static void

die (const char *message)

{

  fprintf (stderr, "%s", message);

  exit (1);

}

/* This bizarro function is from gcov-io.h in gcc source tree */

static int

fetch_long (long        *dest,

            const char  *source,

            size_t       bytes)

{

  long value = 0;

  int i;

  for (i = bytes - 1; (size_t) i > (sizeof (*dest) - 1); i--)

    if (source[i] & ((size_t) i == (bytes - 1) ? 127 : 255 ))

      return 1;

  for (; i >= 0; i--)

    value = value * 256 + (source[i] & ((size_t)i == (bytes - 1) ? 127 : 255));

  if ((source[bytes - 1] & 128) && (value > 0))

    value = - value;

  *dest = value;

  return 0;

}

static int

fetch_long64 (dbus_int64_t *dest,

              const char   *source,

              size_t        bytes)

{

  dbus_int64_t value = 0;

  int i;

  for (i = bytes - 1; (size_t) i > (sizeof (*dest) - 1); i--)

    if (source[i] & ((size_t) i == (bytes - 1) ? 127 : 255 ))

      return 1;

  for (; i >= 0; i--)

    value = value * 256 + (source[i] & ((size_t)i == (bytes - 1) ? 127 : 255));

  if ((source[bytes - 1] & 128) && (value > 0))

    value = - value;

  *dest = value;

  return 0;

}

#define BB_FILENAME 	(-1)

#define BB_FUNCTION 	(-2)

#define BB_ENDOFLIST	0

static dbus_bool_t

string_get_int (const DBusString *str,

                int               start,

                long             *val)

{

  const char *p;

  if ((_dbus_string_get_length (str) - start) < 4)

    return FALSE;

  p = _dbus_string_get_const_data (str);

  p += start;

  fetch_long (val, p, 4);

  return TRUE;

}

static dbus_bool_t

string_get_int64 (const DBusString *str,

                  int               start,

                  dbus_int64_t     *val)

{

  const char *p;

  if ((_dbus_string_get_length (str) - start) < 8)

    return FALSE;

  p = _dbus_string_get_const_data (str);

  p += start;

  fetch_long64 (val, p, 8);

  return TRUE;

}

static dbus_bool_t

string_get_string (const DBusString *str,

                   int               start,

                   long              terminator,

                   DBusString       *val,

                   int              *end)

{

  int i;

  long n;

  i = start;

  while (string_get_int (str, i, &n))

    {

      unsigned char b;

      i += 4;

      if (n == terminator)

        break;

      b = n & 0xff;

      if (b)

        {

          _dbus_string_append_byte (val, b);

          b = (n >> 8) & 0xff;

          if (b)

            {

              _dbus_string_append_byte (val, b);

              b = (n >> 16) & 0xff;

              if (b)

                {

                  _dbus_string_append_byte (val, b);

                  b = (n >> 24) & 0xff;

                  if (b)

                    _dbus_string_append_byte (val, b);

                }

            }

        }

    }

  *end = i;

  return TRUE;

}

#ifdef DBUS_HAVE_GCC33_GCOV

/* In gcc33 .bbg files, there's a function name of the form:

 *   -1, length, name (padded to 4), -1, checksum

 */

static dbus_bool_t

string_get_function (const DBusString *str,

                     int               start,

                     DBusString       *funcname,

                     int              *checksum,

                     int              *next)

{

  int end;

  long val;

  int i;

  i = start;

  if (!string_get_int (str, i, &val))

    die ("no room for -1 before function name\n");

  i += 4;

  if (val != -1)

    die ("value before function name is not -1\n");

  if (!string_get_int (str, i, &val))

    die ("no length found for function name\n");

  i += 4;

  end = i + val;

  if (end > _dbus_string_get_length (str))

    die ("Function name length points past end of file\n");

  if (!_dbus_string_append (funcname,

                            _dbus_string_get_const_data (str) + i))

    die ("no memory\n");

  /* skip alignment padding the length doesn't include the nul so add 1

   */

  i = _DBUS_ALIGN_VALUE (end + 1, 4);

  if (!string_get_int (str, i, &val) ||

      val != -1)

    die ("-1 at end of function name not found\n");

  i += 4;

  if (!string_get_int (str, i, &val))

    die ("no checksum found at end of function name\n");

  i += 4;

  *checksum = val;

  *next = i;

  return TRUE;

}

#endif /* DBUS_HAVE_GCC33_GCOV */

static void

dump_bb_file (const DBusString *contents)

{

  int i;

  long val;

  int n_functions;

  n_functions = 0;

  i = 0;

  while (string_get_int (contents, i, &val))

    {

      i += 4;

      switch (val)

        {

        case BB_FILENAME:

          {

            DBusString f;

            if (!_dbus_string_init (&f))

              die ("no memory\n");

            if (string_get_string (contents, i,

                                   BB_FILENAME,

                                   &f, &i))

              {

                printf ("File %s\n", _dbus_string_get_const_data (&f));

              }

            _dbus_string_free (&f);

          }

          break;

        case BB_FUNCTION:

          {

            DBusString f;

            if (!_dbus_string_init (&f))

              die ("no memory\n");

            if (string_get_string (contents, i,

                                   BB_FUNCTION,

                                   &f, &i))

              {

                printf ("Function %s\n", _dbus_string_get_const_data (&f));

              }

            _dbus_string_free (&f);

            n_functions += 1;

          }

          break;

        case BB_ENDOFLIST:

          printf ("End of block\n");

          break;

        default:

          printf ("Line %ld\n", val);

          break;

        }

    }

  printf ("%d functions in file\n", n_functions);

}

#define FLAG_ON_TREE 0x1

#define FLAG_FAKE 0x2

#define FLAG_FALL_THROUGH 0x4

static void

dump_bbg_file (const DBusString *contents)

{

  int i;

  long val;

  int n_functions;

  int n_arcs;

  int n_blocks;

  int n_arcs_off_tree;

  n_arcs_off_tree = 0;

  n_blocks = 0;

  n_arcs = 0;

  n_functions = 0;

  i = 0;

  while (i < _dbus_string_get_length (contents))

    {

      long n_blocks_in_func;

      long n_arcs_in_func; 

      int j;

#ifdef DBUS_HAVE_GCC33_GCOV

      /* In gcc33 .bbg files, there's a function name of the form:

       *   -1, length, name (padded to 4), -1, checksum

       * after that header on each function description, it's

       * the same as in gcc32

       */

      {

        DBusString funcname;

        int checksum;

        if (!_dbus_string_init (&funcname))

          die ("no memory\n");

        if (!string_get_function (contents, i,

                                  &funcname, &checksum, &i))

          die ("could not read function name\n");

        printf ("Function name is \"%s\" checksum %d\n",

                _dbus_string_get_const_data (&funcname),

                checksum);

        _dbus_string_free (&funcname);

      }

#endif /* DBUS_HAVE_GCC33_GCOV */

      if (!string_get_int (contents, i, &val))

        die ("no count of blocks in func found\n");

      i += 4;

      n_blocks_in_func = val;

      if (!string_get_int (contents, i, &n_arcs_in_func))

        break;

      i += 4;

      printf ("Function has %ld blocks and %ld arcs\n",

              n_blocks_in_func, n_arcs_in_func);

      n_functions += 1;

      n_blocks += n_blocks_in_func;

      n_arcs += n_arcs_in_func;

      j = 0;

      while (j < n_blocks_in_func)

        {

          long n_arcs_in_block;

          int k;

          if (!string_get_int (contents, i, &n_arcs_in_block))

            break;

          i += 4;

          printf ("  Block has %ld arcs\n", n_arcs_in_block);

          k = 0;

          while (k < n_arcs_in_block)

            {

              long destination_block;

              long flags;

              if (!string_get_int (contents, i, &destination_block))

                break;

              i += 4;

              if (!string_get_int (contents, i, &flags))

                break;

              i += 4;

              printf ("    Arc has destination block %ld flags 0x%lx\n",

                      destination_block, flags);

              if ((flags & FLAG_ON_TREE) == 0)

                n_arcs_off_tree += 1;

              ++k;

            }

          if (k < n_arcs_in_block)

            break;

          ++j;

        }

      if (j < n_blocks_in_func)

        break;

      if (!string_get_int (contents, i, &val))

        break;

      i += 4;

      if (val != -1)

        die ("-1 separator not found\n");

    }

  printf ("%d functions %d blocks %d arcs %d off-tree arcs in file\n",

          n_functions, n_blocks, n_arcs, n_arcs_off_tree);

}

#ifndef DBUS_HAVE_GCC33_GCOV

/* gcc 3.2 version:

 * The da file contains first a count of arcs in the file,

 * then a count of executions for all "off tree" arcs

 * in the file.

 */

static void

dump_da_file (const DBusString *contents)

{

  int i;

  dbus_int64_t val;

  int n_arcs;

  int claimed_n_arcs;

  i = 0;

  if (!string_get_int64 (contents, i, &val))

    return;

  i += 8;

  printf ("%ld arcs in file\n", (long) val);

  claimed_n_arcs = val;

  n_arcs = 0;

  while (string_get_int64 (contents, i, &val))

    {

      i += 8;

      printf ("%ld executions of arc %d\n",

              (long) val, n_arcs);

      ++n_arcs;

    }

  if (n_arcs != claimed_n_arcs)

    {

      printf ("File claimed to have %d arcs but only had %d\n",

              claimed_n_arcs, n_arcs);

    }

}

#else /* DBUS_HAVE_GCC33_GCOV */

/* gcc 3.3 version:

 * The da file is more complex than 3.2.

 *

 * We have a magic value of "-123" only it isn't really

 * -123, it's -123 as encoded by the crackass gcov-io.h

 * routines. Anyway, 4 bytes.

 *

 * We then have:

 *

 *   - 4 byte count of how many functions in the following list

 *   - 4 byte length of random extra data

 *   - the random extra data, just skip it, info pages have some

 *     details on what might be in there or see __bb_exit_func in gcc

 *   - then for each function (number of functions given above):

 *     . -1, length, funcname, alignment padding, -1

 *     . checksum

 *     . 4 byte number of arcs in function

 *     . 8 bytes each, a count of execution for each arc

 *

 * Now, the whole thing *starting with the magic* can repeat.

 * This is caused by multiple runs of the profiled app appending

 * to the file.

 */

static void

dump_da_file (const DBusString *contents)

{

  int i;

  dbus_int64_t v64;

  long val;

  int n_sections;

  int total_functions;

  total_functions = 0;

  n_sections = 0;

  i = 0;

  while (i < _dbus_string_get_length (contents))

    {

      int claimed_n_functions;

      int n_functions;

      int total_arcs;

      printf (".da file section %d\n", n_sections);

      if (!string_get_int (contents, i, &val))

        die ("no magic found in .da file\n");

      i += 4;

      if (val != -123)

        die ("wrong file magic in .da file\n");

      if (!string_get_int (contents, i, &val))

        die ("no function count in .da file\n");

      i += 4;

      claimed_n_functions = val;

      printf ("%d functions expected in section %d of .da file\n",

              claimed_n_functions, n_sections);

      if (!string_get_int (contents, i, &val))

        die ("no extra data length in .da file\n");

      i += 4;

      i += val;

      total_arcs = 0;

      n_functions = 0;

      while (n_functions < claimed_n_functions)

        {

          DBusString funcname;

          int checksum;

          int claimed_n_arcs;

          int n_arcs;

          if (!_dbus_string_init (&funcname))

            die ("no memory\n");

          if (!string_get_function (contents, i,

                                    &funcname, &checksum, &i))

            die ("could not read function name\n");

          if (!string_get_int (contents, i, &val))

            die ("no arc count for function\n");

          i += 4;

          claimed_n_arcs = val;

          printf ("  %d arcs in function %d %s checksum %d\n",

                  claimed_n_arcs, n_functions,

                  _dbus_string_get_const_data (&funcname),

                  checksum);

          n_arcs = 0;

          while (n_arcs < claimed_n_arcs)

            {

              if (!string_get_int64 (contents, i, &v64))

                die ("did not get execution count for arc\n");

              i += 8;

              printf ("    %ld executions of arc %d (total arcs %d)\n",

                      (long) v64, n_arcs, total_arcs + n_arcs);

              ++n_arcs;

            }

          _dbus_string_free (&funcname);

          total_arcs += n_arcs;

          ++n_functions;

        }

      printf ("total of %d functions and %d arcs in section %d\n",

              n_functions, total_arcs, n_sections);

      total_functions += n_functions;

      ++n_sections;

    }

  printf ("%d total function sections in %d total .da file sections\n",

          total_functions, n_sections);

}

#endif /* DBUS_HAVE_GCC33_GCOV */

typedef struct Arc Arc;

typedef struct Block Block;

typedef struct Function Function;

typedef struct File File;

typedef struct Line Line;

struct Arc

{

  int source;

  int target;

  dbus_int64_t arc_count;

  unsigned int count_valid : 1;

  unsigned int on_tree : 1;

  unsigned int fake : 1;

  unsigned int fall_through : 1;

  Arc *pred_next;

  Arc *succ_next;

};

struct Block

{

  Arc *succ;

  Arc *pred;

  dbus_int64_t succ_count;

  dbus_int64_t pred_count;

  dbus_int64_t exec_count;

  DBusList *lines;

  unsigned int count_valid : 1;

  unsigned int on_tree : 1;

  unsigned int inside_dbus_build_tests : 1;

};

struct Function

{

  char *name;

  int checksum;

  Block *block_graph;

  int n_blocks;

  /* number of blocks in DBUS_BUILD_TESTS */

  int n_test_blocks;

  int n_test_blocks_executed;

  /* number of blocks outside DBUS_BUILD_TESTS */

  int n_nontest_blocks;

  int n_nontest_blocks_executed;

  /* Summary result flags */

  unsigned int unused : 1;

  unsigned int inside_dbus_build_tests : 1;

  unsigned int partial : 1; /* only some of the blocks were executed */

};

struct Line

{

  int    number;

  char  *text;

  DBusList *blocks;

  unsigned int inside_dbus_build_tests : 1;

  unsigned int partial : 1; /* only some of the blocks were executed */

};

struct File

{

  char *name;

  Line *lines;

  int   n_lines;

  DBusList *functions;

};

static void

function_add_arc (Function *function,

                  long      source,

                  long      target,

                  long      flags)

{

  Arc *arc;

  arc = dbus_new0 (Arc, 1);

  if (arc == NULL)

    die ("no memory\n");

  arc->target = target;

  arc->source = source;

  arc->succ_next = function->block_graph[source].succ;

  function->block_graph[source].succ = arc;

  function->block_graph[source].succ_count += 1;

  arc->pred_next = function->block_graph[target].pred;

  function->block_graph[target].pred = arc;

  function->block_graph[target].pred_count += 1;

  if ((flags & FLAG_ON_TREE) != 0)

    arc->on_tree = TRUE;

  if ((flags & FLAG_FAKE) != 0)

    arc->fake = TRUE;

  if ((flags & FLAG_FALL_THROUGH) != 0)

    arc->fall_through = TRUE;

}

static Arc*

reverse_arcs (Arc *arc)

{

  struct Arc *prev = 0;

  struct Arc *next;

  for ( ; arc; arc = next)

    {

      next = arc->succ_next;

      arc->succ_next = prev;

      prev = arc;

    }

  return prev;

}

static void

function_reverse_succ_arcs (Function *func)

{

  /* Must reverse the order of all succ arcs, to ensure that they match

   * the order of the data in the .da file.

   */

  int i;

  for (i = 0; i < func->n_blocks; i++)

    if (func->block_graph[i].succ)

      func->block_graph[i].succ = reverse_arcs (func->block_graph[i].succ);

}

static void

get_functions_from_bbg (const DBusString  *contents,

                        DBusList         **functions)

{

  int i;

  long val;

  int n_functions;

  int n_arcs;

  int n_blocks;

  int n_arcs_off_tree;

#if 0

  printf ("Loading arcs and blocks from .bbg file\n");

#endif

  n_arcs_off_tree = 0;

  n_blocks = 0;

  n_arcs = 0;

  n_functions = 0;

  i = 0;

  while (i < _dbus_string_get_length (contents))

    {

      Function *func;

      long n_blocks_in_func;

      long n_arcs_in_func; 

      int j;

#ifdef DBUS_HAVE_GCC33_GCOV

      DBusString funcname;

      int checksum;

      /* In gcc33 .bbg files, there's a function name of the form:

       *   -1, length, name (padded to 4), -1, checksum

       * after that header on each function description, it's

       * the same as in gcc32

       */

      if (!_dbus_string_init (&funcname))

        die ("no memory\n");

      if (!string_get_function (contents, i,

                                &funcname, &checksum, &i))

        die ("could not read function name\n");

#endif /* DBUS_HAVE_GCC33_GCOV */

      if (!string_get_int (contents, i, &val))

        break;

      n_blocks_in_func = val;

      i += 4;

      if (!string_get_int (contents, i, &n_arcs_in_func))

        break;

      i += 4;

      n_functions += 1;

      n_blocks += n_blocks_in_func;

      n_arcs += n_arcs_in_func;

      func = dbus_new0 (Function, 1);

      if (func == NULL)

        die ("no memory\n");

#ifdef DBUS_HAVE_GCC33_GCOV

      func->name = _dbus_strdup (_dbus_string_get_const_data (&funcname));

      func->checksum = checksum;

      _dbus_string_free (&funcname);

#endif

      func->block_graph = dbus_new0 (Block, n_blocks_in_func);

      func->n_blocks = n_blocks_in_func;

      j = 0;

      while (j < n_blocks_in_func)

        {

          long n_arcs_in_block;

          int k;

          if (!string_get_int (contents, i, &n_arcs_in_block))

            break;

          i += 4;

          k = 0;

          while (k < n_arcs_in_block)

            {

              long destination_block;

              long flags;

              if (!string_get_int (contents, i, &destination_block))

                break;

              i += 4;

              if (!string_get_int (contents, i, &flags))

                break;

              i += 4;

              if ((flags & FLAG_ON_TREE) == 0)

                n_arcs_off_tree += 1;

              function_add_arc (func, j, destination_block,

                                flags);

              ++k;

            }

          if (k < n_arcs_in_block)

            break;

          ++j;

        }

      if (j < n_blocks_in_func)

        break;

      function_reverse_succ_arcs (func);

      if (!_dbus_list_append (functions, func))

        die ("no memory\n");

      if (!string_get_int (contents, i, &val))

        break;

      i += 4;

      if (val != -1)

        die ("-1 separator not found in .bbg file\n");

    }

#if 0

  printf ("%d functions %d blocks %d arcs %d off-tree arcs in file\n",

          n_functions, n_blocks, n_arcs, n_arcs_off_tree);

#endif

  _dbus_assert (n_functions == _dbus_list_get_length (functions));

}

#ifdef DBUS_HAVE_GCC33_GCOV

static void

add_counts_from_da (const DBusString  *contents,

                    DBusList         **functions)

{

  int i;

  dbus_int64_t v64;

  long val;

  int n_sections;

  DBusList *link;

  Function *current_func;  

  int current_block;

  Arc *current_arc;

  n_sections = 0;

  i = 0;

  while (i < _dbus_string_get_length (contents))

    {

      int claimed_n_functions;

      int n_functions;

      if (!string_get_int (contents, i, &val))

        die ("no magic found in .da file\n");

      i += 4;

      if (val != -123)

        die ("wrong file magic in .da file\n");

      if (!string_get_int (contents, i, &val))

        die ("no function count in .da file\n");

      i += 4;

      claimed_n_functions = val;

      if (!string_get_int (contents, i, &val))

        die ("no extra data length in .da file\n");

      i += 4;

      i += val;

      link = _dbus_list_get_first_link (functions);

      if (link == NULL)

        goto no_more_functions;

      n_functions = 0;

      while (n_functions < claimed_n_functions && link != NULL)

        {

          DBusString funcname;

          int checksum;

          int claimed_n_arcs;

          int n_arcs;

          current_func = link->data;

          current_block = 0;

          current_arc = current_func->block_graph[current_block].succ;

          if (!_dbus_string_init (&funcname))

            die ("no memory\n");

          if (!string_get_function (contents, i,

                                    &funcname, &checksum, &i))

            die ("could not read function name\n");

          if (!_dbus_string_equal_c_str (&funcname, current_func->name))

            {

              fprintf (stderr, "Expecting .da info for %s but got %s\n",

                       current_func->name,

                       _dbus_string_get_const_data (&funcname));

              exit (1);

            }

          if (checksum != current_func->checksum)

            die (".da file checksum doesn't match checksum from .bbg file\n");

          if (!string_get_int (contents, i, &val))

            die ("no arc count for function\n");

          i += 4;

          claimed_n_arcs = val;

          /* For each arc in the profile, find the corresponding

           * arc in the function and increment its count

           */

          n_arcs = 0;

          while (n_arcs < claimed_n_arcs)

            {

              if (!string_get_int64 (contents, i, &v64))

                die ("did not get execution count for arc\n");

              i += 8;

              /* Find the next arc in the function that isn't on tree */

              while (current_arc == NULL ||

                     current_arc->on_tree)

                {

                  if (current_arc == NULL)

                    {

                      ++current_block;

                      if (current_block >= current_func->n_blocks)

                        die ("too many blocks in function\n");

                      current_arc = current_func->block_graph[current_block].succ;