/*

Copyright (C) 2000 - 2006 Christian Kreibich <christian@whoop.org>.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to
deal in the Software without restriction, including without limitation the
rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
sell copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies of the Software and its documentation and acknowledgment shall be
given in the documentation and software packages that this Software was
used.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/


#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

#include <sys/types.h>
#include <stdio.h>
#include <errno.h>
#include <libnd_tpm.h>

#include <libnd_trace.h>
#include <libnd_prefs.h>
#include <libnd_tcpdump.h>
#include <libnd_tp.h>

#define LND_BASENAME_PFX  "netdude-base-"

static void
tpm_dump_part(LND_TracePart *tp)
{
  if (!tp)
    {
      printf("Part is NULL\n");
      return;
    }
  
  printf("Part %p: size %lu, start at %lu in %p, end at %lu in %p, infile: %s, outfile %s\n",
	 tp,
	 (long unsigned) tp->size,
	 (long unsigned) tp->start.offset, tp->start.tp,
	 (long unsigned) tp->end.offset, tp->end.tp,
	 tp->in_filename, tp->out_filename);
}

static LND_TracePart *
tp_get_first_part(LND_TracePart *tp)
{
  if (!tp || !tp->parts)
    return NULL;

  return (LND_TracePart *) tp->parts->data;
}

void
libnd_tpm_dump_parts(LND_TPM *tpm)
{
  LND_TracePart *tp, *next_part;
  
  D_ENTER;

  printf("Current part:\n");
  tpm_dump_part(tpm->current);
  
  printf("Other parts:\n");
  tp = tpm->base;
  next_part = tp_get_first_part(tpm->base);
  
  while (tp)
    {
      tpm_dump_part(tp);
      if (! next_part)
	{
	  /* This is a "plateau" -- check if our offset is within
	   * the plateau, otherwise fall off the end.
	   */
	  printf("Down to %p, at %lu\n", tp->end.tp, (long unsigned) tp->end.offset);

	  next_part = libnd_tp_find_part_after_offset(tp->end.tp, tp->end.offset, tp);
	  tp = tp->end.tp;
	  continue;
	}
      
      printf("Up to %p, at %lu\n", next_part, (long unsigned) next_part->start.offset);
      tp = next_part;
      next_part = tp_get_first_part(tp);
    }
  
  D_RETURN;
}  


LND_TPM         *
libnd_tpm_new(LND_Trace *trace)
{
  LND_TPM *tpm = g_new0(LND_TPM, 1);

  D_ENTER;
  D_ASSERT_PTR(tpm);

  D(("Creating TPM for trace '%s'\n", trace->filename));

  if (!tpm)
    D_RETURN_(NULL);

  tpm->trace = trace;
  tpm->base = libnd_tp_new(tpm, NULL, 0);

  if (trace->filename)
    {
      if (! libnd_tp_set_input_file(tpm->base, trace->filename))
	{
	  D(("Could not set base's filename\n"));
	  D_RETURN_(tpm);
	}

      tpm->size = tpm->base->end.offset;
      D(("TPM base size: %lu\n", (long unsigned) tpm->base->end.offset));
      tpm->output_name = libnd_misc_get_tmpfile(trace->filename);
    }

  tpm->current = libnd_tp_new(tpm, tpm->base, 0);

  D_RETURN_(tpm);
}


void            
libnd_tpm_free(LND_TPM *tpm)
{
  D_ENTER;

  if (!tpm)
    D_RETURN;

  /* This recursively cleans up everything sitting on top */
  libnd_tp_free(tpm->base);

  /* The current part is not yet part of the pile, so needs
   * to be cleaned up separately.
   */
  libnd_tp_free(tpm->current);
  
  g_free(tpm->output_name);
  g_free(tpm);

  D_RETURN;
}


void
libnd_tpm_load_packets(LND_TPM *tpm)
{
  LND_Packet tmp_packet;
  guint num_mem_packets = libnd_tpm_num_memory_packets();
  guint i;

  D_ENTER;
  
  if (!tpm || !tpm->trace || !tpm->trace->filename)
    D_RETURN;
  
  D_ASSERT_PTR(tpm->current);
  if (!tpm->current)
    D_RETURN;

  memset(&tmp_packet, 0, sizeof(LND_Packet));

  for (i = tpm->current->num_packets; i < num_mem_packets; i++)
    {
      if (! libnd_tpm_read_packet(tpm, &tmp_packet))
	break;

      libnd_tpm_pcap_read_handler((u_char *) tpm->current, &tmp_packet.ph, tmp_packet.data);      
    }

  libnd_tp_init_packets(tpm->current); 

  /* If the trace consists of just the loaded packets, there's no
   * need for navigation.
   */
  tpm->trace->needs_nav =
    ! (tpm->current->start.tp     == tpm->base &&
       tpm->current->start.offset == 0         &&
       tpm->current->end.tp       == tpm->base &&
       tpm->current->end.offset   == tpm->size);

  libnd_trace_tell_observers(tpm->trace, LND_TRACE_RELOAD);
			   
  D_RETURN;
}


void             
libnd_tpm_load_prev_part(LND_TPM *tpm)
{
  LND_TraceLoc loc, stop_loc;
  off_t start_off, blocksize, offset;
  const struct pcap_file_header *fh;
  pcapnav_result_t result;
  guint num_mem_packets = libnd_tpm_num_memory_packets();
  LND_Packet tmp_packet, *packet;

  D_ENTER;

  if (!tpm || !tpm->current)
    {
      D(("Input error.\n"));
      D_RETURN;
    }

  /* Jumping back one part is harder than jumping to the
   * next part, since we don't know exactly how far to jump back.
   * We jump back the number of packets to load in memory
   * times the maximum size of a packet, in bytes. Then we
   * load packets into memory from there on, and drop packets
   * at the beginning while we haven't yet reached the previously
   * first packet.
   */
  if (! (fh = pcapnav_get_file_header(tpm->base->pcn)))
    {
      D(("File header not available\n"));
      D_RETURN;
    }

  blocksize =
    libnd_tpm_num_memory_packets() *
    (pcapnav_get_pkthdr_size(tpm->current->pcn) + fh->snaplen);

  stop_loc = tpm->current->start;
  offset = start_off = libnd_tpm_map_loc_to_offset(tpm, &tpm->current->start);

  if (start_off == 0)
    {
      D(("Already at start of trace.\n"));
      D_RETURN;
    }

  offset -= MIN(offset, blocksize);

  /* Get the offset of actual packet start */
  result = libnd_tpm_map_offset_to_loc(tpm, offset, &loc);
  offset = libnd_tpm_map_loc_to_offset(tpm, &loc);
  D(("Starting previous part at part %p, global offset %lu\n",
     loc.tp, (long unsigned) offset));

  /* This is a prelimiary jump; we still need to find the correct
   * location afterwards. Therefore do not fire any JUMPED events.
   */
  libnd_trace_block_trace_observer_op(tpm->trace, LND_TRACE_JUMPED);
  libnd_tpm_goto_loc(tpm, &loc);
  libnd_trace_unblock_trace_observer_op(tpm->trace, LND_TRACE_JUMPED);

  /* Handle packet loading manually */
  memset(&tmp_packet, 0, sizeof(LND_Packet));

  D(("Ending previous part at part %p, offset %lu\n",
     stop_loc.tp, (long unsigned) stop_loc.offset));

  /* Read packets until we hit the start of the former trace part.
   * Keep reading in case there are not enough packets in memory
   * at that point.
   */
  while (! (tpm->current->end.tp == stop_loc.tp &&
	    tpm->current->end.offset >= stop_loc.offset) ||
	 tpm->current->num_packets < libnd_tpm_num_memory_packets())
    {
      D(("Loading packet %i\n", tpm->current->num_packets));
      libnd_tpm_read_packet(tpm, &tmp_packet);
      libnd_tpm_pcap_read_handler((u_char *) tpm->current, &tmp_packet.ph, tmp_packet.data);
      
      if (tpm->current->num_packets > num_mem_packets)
	{
	  packet = tpm->current->pl;

	  tpm->current->pl = packet->next;
	  tpm->current->pl->prev = NULL;
	  tpm->current->num_packets--;
	  tpm->current->size -= pcapnav_get_pkthdr_size(tpm->current->pcn) + packet->ph.caplen;
	  offset += pcapnav_get_pkthdr_size(tpm->current->pcn) + packet->ph.caplen;
	  D(("Dropping one, start offset now %lu\n", (long unsigned) offset));

	  libnd_packet_free(packet);
	}
    }

  /* Now fix start location and timestamp, after we maybe dropped packets */
  if (tpm->current->pl)
    tpm->current->start_ts = tpm->current->pl->ph.ts;
  libnd_tpm_map_offset_to_loc(tpm, offset, &tpm->current->start);

  D(("Previous part starts at %p, %lu\n", tpm->current->start.tp,
     (long unsigned) tpm->current->start.offset));

  libnd_tp_init_packets(tpm->current); 
  
  /* If the trace has only a few packets, don't allow the
   * user to open the trace navigation dialog: */
  tpm->trace->needs_nav = (tpm->current->end.tp || pcapnav_has_next(tpm->current->pcn));
  libnd_trace_tell_observers(tpm->trace, LND_TRACE_RELOAD);

  D_RETURN;
}


void
libnd_tpm_load_next_part(LND_TPM *tpm)
{
  D_ENTER;
  
  if (!tpm || !tpm->current)
    {
      D(("Input error.\n"));
      D_RETURN;
    }

  /* If we're at the end of the trace, don't do anything */
  if (tpm->base->end.offset == tpm->current->end.offset)
    D_RETURN;

  /* This is a prelimiary jump; we still need to find the correct
   * location afterwards. Therefore do not fire any JUMPED events.
   */
  libnd_trace_block_trace_observer_op(tpm->trace, LND_TRACE_JUMPED);
  libnd_tpm_goto_loc(tpm, &tpm->current->end);
  libnd_trace_unblock_trace_observer_op(tpm->trace, LND_TRACE_JUMPED);

  libnd_tpm_load_packets(tpm);

  D_RETURN;
}


gboolean         
libnd_tpm_read_packet(LND_TPM *tpm, LND_Packet *packet)
{
  gboolean result;

  D_ENTER;

  if (!tpm || !tpm->current || !packet)
    D_RETURN_(FALSE);

  libnd_packet_cleanup(packet);
  D_ASSERT_PTR(tpm->current->end.tp);

  /* Check if we have to jump up to a different part */
  if (tpm->current->next_part)
    {
      D(("Not plateau, currently at %lu, next part starts at %lu\n",
	 pcapnav_get_offset(tpm->current->pcn), tpm->current->next_part->start.offset));
      
      if (pcapnav_get_offset(tpm->current->pcn) == tpm->current->next_part->start.offset)
	{
	  D(("Need to jump up to next_part %p\n", tpm->current->next_part));
	  pcapnav_close(tpm->current->pcn);
	  tpm->current->pcn = NULL;

	  tpm->current->end.tp = tpm->current->next_part;
	  tpm->current->end.offset = 0;

	  if (! (tpm->current->pcn = pcapnav_open_offline(tpm->current->end.tp->in_filename)))
	    {
	      D(("Could not jump up to next part\n"));
	      D_RETURN_(FALSE);
	    }

	  tpm->current->next_part = tp_get_first_part(tpm->current->end.tp);

	  /* We may need to jump up again if the next part starts right
	   * away. The easiest way to detect that is to just try again:
	   */
	  result = libnd_tpm_read_packet(tpm, packet);
	  D_RETURN_(result);
	}
    }

  /* Now try to read a packet */
  D(("Reading from part %p, offset %lu\n", tpm->current->end.tp,
     (long unsigned) pcapnav_get_offset(tpm->current->pcn)));
  packet->data = (u_char *) pcapnav_next(tpm->current->pcn, &packet->ph);

  /* If it didn't work, we need to fall off the end of a part */
  if (!packet->data)
    {
      LND_TracePart *tp_dontuse;

      if (! tpm->current->end.tp->end.tp)
	{
	  D(("EOF -- cannot read next packet!\n"));
	  D_RETURN_(FALSE);
	}
           
      pcapnav_close(tpm->current->pcn);
      tpm->current->pcn = NULL;
      tp_dontuse = tpm->current->end.tp;
      tpm->current->end.offset = tpm->current->end.tp->end.offset;
      tpm->current->end.tp     = tpm->current->end.tp->end.tp;
      D(("Falling down to part %p at %lu\n",
	 tpm->current->end.tp,
	 (long unsigned) tpm->current->end.offset));

      if (! (tpm->current->pcn = pcapnav_open_offline(tpm->current->end.tp->in_filename)))
	{
	  D(("Could not fall down to end part\n"));
	  D_RETURN_(FALSE);
	}

      if (pcapnav_set_offset(tpm->current->pcn, tpm->current->end.offset) < 0)
	{
	  D(("Could not jump to end part's offset\n"));
	  D_RETURN_(FALSE);
	}

      /* Make sure we cannot use the same part twice, hence tp_dontuse ...*/
      tpm->current->next_part = libnd_tp_find_part_after_offset(tpm->current->end.tp,
								tpm->current->end.offset,
								tp_dontuse);
      /* This new next part may be starting right where we just
       * fell down to, so just recurse and try again.
       */
      result = libnd_tpm_read_packet(tpm, packet);
      D_RETURN_(result);
    }

  if (packet->data)
    {
      /* Does NOT add the packet to the current part, hence
       * no increment of packet count.
       */
      packet->part = tpm->current;
      tpm->current->end.offset += sizeof(struct pcap_pkthdr) + packet->ph.caplen;
    }

  D_RETURN_(TRUE);
}


void             
libnd_tpm_set_output_file(LND_TPM *tpm, const char *filename)
{
  if (!tpm || !filename || !*filename)
    return;
  
  g_free(tpm->output_name);
  tpm->output_name = g_strdup(filename);
  D(("Output filename set to %s\n", tpm->output_name));
}


guint
libnd_tpm_num_memory_packets()
{
  guint num_mem_packets;

  libnd_prefs_get_int_item(LND_DOM_NETDUDE,
			"num_mem_packets",
			&num_mem_packets);

  return num_mem_packets;
}


static gint
tpm_parts_cmp_inc(const LND_TracePart *tp1, const LND_TracePart *tp2)
{
  /* tp1 is the inserted item, tp2 the list item, according to
   * glib 1.2.10 sources. */

  if (tp1->start.offset <= tp2->start.offset)
    return 0;

  return 1;
}


static gint
tpm_parts_cmp_dec(const LND_TracePart *tp1, const LND_TracePart *tp2)
{
  /* tp1 is the inserted item, tp2 the list item, according to
   * glib 1.2.10 sources. */

  if (tp1->start.offset >= tp2->start.offset)
    return 0;

  return 1;
}


void
libnd_tpm_clear_current_part(LND_TPM *tpm, gboolean emit_signal)
{
  D_ENTER;

  if (!tpm || !tpm->current)
    D_RETURN;

  if (tpm->current->dirty)
    libnd_tp_sync(tpm->current);
  else if (! tpm->current->anchored)
    libnd_tp_free(tpm->current);

  if (emit_signal)
    libnd_trace_tell_observers(tpm->trace, LND_TRACE_CLEAR);

  tpm->current = NULL;

  D_RETURN;
}


void             
libnd_tpm_add_part(LND_TPM *tpm, LND_TracePart *tp)
{
  LND_TraceLoc loc;
  off_t start_off, end_off;

  D_ENTER;

  if (!tpm || !tp)
    D_RETURN;

  D_ASSERT_PTR(tp->start.tp);
  D_ASSERT_PTR(tp->end.tp);

  if (!tp->start.tp || !tp->end.tp)
    {
      D(("No start and end part in part %p, not adding.\n", tp));
      D_RETURN;
    }

  /* Update the size of the entire trace, by comparing the size that the
   * trace part covers to the size it provides. If it provides less than
   * it covers, the trace effectively shrinks, otherwise it increases.
   */
  loc.tp = tp->start.tp;
  loc.offset = tp->start.offset;
  start_off = libnd_tpm_map_loc_to_offset(tpm, &loc);
  D(("New part's start offset: %lu\n", (long unsigned) start_off));

  loc.tp = tp->end.tp;
  loc.offset = tp->end.offset;
  end_off = libnd_tpm_map_loc_to_offset(tpm, &loc);
  D(("New part's end offset: %lu\n", (long unsigned) end_off));
  
  /* Don't modify global size here -- already done whenever packets
   * are added/removed while in memory!
   *
   * D(("Trace size changes from %lu by %li\n",
   *  (long unsigned) tpm->size, tp->size - ((int)end_off - (int)start_off)));
   * tpm->size += tp->size - ((int)end_off - (int)start_off);
   */

  /* Update the data structures for forward iteration */
  if (! g_list_find(tp->start.tp->parts, tp))
    {
      tp->start.tp->parts = g_list_insert_sorted(tp->start.tp->parts, tp,
						 (GCompareFunc) tpm_parts_cmp_inc);
    }

  /* ... and update the data structures for backward iteration */  
  if (! g_list_find(tp->end.tp->bw_parts, tp))
    {  
      tp->end.tp->bw_parts = g_list_insert_sorted(tp->end.tp->bw_parts, tp,
						  (GCompareFunc) tpm_parts_cmp_dec);
    }

  tp->tpm = tpm;
  tp->anchored = TRUE;

  D_RETURN;
}


gboolean
libnd_tpm_remove_part(LND_TPM *tpm, LND_TracePart *tp)
{
  if (!tpm || !tp)
    return FALSE;

  if (tp->parts)
    return FALSE;

  if (tp->start.tp)
    {
      g_list_remove(tp->start.tp->parts, tp);
      g_list_remove(tp->start.tp->bw_parts, tp);
    }

  if (tp->end.tp)
    {
      g_list_remove(tp->end.tp->parts, tp);
      g_list_remove(tp->end.tp->bw_parts, tp);
    }

  tp->tpm = NULL;
  tp->anchored = FALSE;

  return TRUE;
}


pcapnav_result_t  
libnd_tpm_goto_ts(LND_TPM *tpm, struct bpf_timeval *timestamp)
{
  LND_TracePart *tp;
  LND_TraceLoc   loc;
  pcapnav_result_t    result;
  
  D_ENTER;

  if (!tpm || !timestamp)
    D_RETURN_(PCAPNAV_ERROR);

  result = libnd_tpm_map_timestamp_to_loc(tpm, timestamp, &loc);
  if (result != PCAPNAV_DEFINITELY &&
      result != PCAPNAV_PERHAPS)    
    D_RETURN_(result);
  
  if ( (tp = libnd_tp_new(tpm, loc.tp, loc.offset)))
    {
      libnd_tpm_clear_current_part(tpm, FALSE);
      tpm->current = tp;
      libnd_trace_tell_observers(tpm->trace, LND_TRACE_JUMPED);
    }

  D_RETURN_(result);
}


pcapnav_result_t  
libnd_tpm_goto_fraction(LND_TPM *tpm, double fraction)
{
  LND_TracePart *tp;
  LND_TraceLoc loc;
  pcapnav_result_t  result = PCAPNAV_DEFINITELY;

  D_ENTER;

  if (!tpm)
    D_RETURN_(PCAPNAV_ERROR);

  /* Map the offset to one in the current trace scenario, taking into
   * account the swapped-out parts and any insertions/deletions made
   * in the various trace parts:
   */
  result = libnd_tpm_map_fraction_to_loc(tpm, fraction, &loc);
  if (result != PCAPNAV_DEFINITELY &&
      result != PCAPNAV_PERHAPS)    
    D_RETURN_(result);

  D_ASSERT_PTR(loc.tp);
  if ( (tp = libnd_tp_new(tpm, loc.tp, loc.offset)))
    {
      libnd_tpm_clear_current_part(tpm, FALSE);
      tpm->current = tp;
      libnd_trace_tell_observers(tpm->trace, LND_TRACE_JUMPED);
    }
  
  D_RETURN_(result);
}


gboolean
libnd_tpm_goto_loc(LND_TPM *tpm, LND_TraceLoc *loc)
{
  LND_TraceLoc loc_copy;

  D_ENTER;
  
  if (!tpm || !loc || !loc->tp)
    {
      D(("Input error\n"));
      D_RETURN_(FALSE);
    }
  
#ifdef LIBND_DEBUG
  if (libnd_runtime_options.debug)
    {
      D(("Parts before jumping to new loc\n"));
      libnd_tpm_dump_parts(tpm);
    }
#endif

  D(("Jumping to location: part %p, offset %lu\n",
     loc->tp, (long unsigned) loc->offset));

  /* Make a copy of the trace location, as it might be
   * a pointer into current trace (e.g. &tpm->current->end)
   * part we're about to free().
   */
  loc_copy = *loc;
  
  libnd_tpm_clear_current_part(tpm, FALSE);
  if (! (tpm->current = libnd_tp_new(tpm, loc_copy.tp, loc_copy.offset)))
    D_RETURN_(FALSE);
  
#ifdef LIBND_DEBUG
  if (libnd_runtime_options.debug)
    {
      D(("Current parts after jumping:\n"));
      libnd_tpm_dump_parts(tpm);
    }
#endif

  libnd_trace_tell_observers(tpm->trace, LND_TRACE_JUMPED);

  D_RETURN_(TRUE);
}


gboolean           
libnd_tpm_is_tp_overlap(const LND_TPM *tpm,
			const LND_TracePart *tp1,
			const LND_TracePart *tp2)
{
  off_t start_off1, start_off2, end_off1, end_off2;

  if (!tp1 || !tp2)
    return FALSE;

  start_off1 = libnd_tpm_map_loc_to_offset(tpm, &tp1->start);
  end_off1   = libnd_tpm_map_loc_to_offset(tpm, &tp1->end);
  start_off2 = libnd_tpm_map_loc_to_offset(tpm, &tp2->start);
  end_off2   = libnd_tpm_map_loc_to_offset(tpm, &tp2->end);
  
  if (start_off1 <= start_off2 &&
      start_off2 <= end_off1)
    return TRUE;

  if (start_off2 <= start_off1 &&
      start_off1 <= end_off2)
    return TRUE;

  return FALSE;
}


off_t
libnd_tpm_map_loc_to_offset(const LND_TPM *tpm, const LND_TraceLoc *loc)
{
  LND_TracePart *tp, *next_part;
  off_t          offset, current;

  D_ENTER;

  if (!tpm || !loc)
    D_RETURN_(0);
  
  tp = tpm->base;
  offset = current = 0;
  next_part = tp_get_first_part(tp);

  while (tp)
    {
      if (! next_part)
	{

	  if (loc->tp == tp)
	    {
	      offset += (loc->offset - current);
	      break;
	    }

	  current = tp->end.offset;
	  offset += tp->size;
	  next_part = libnd_tp_find_part_after_offset(tp->end.tp,
						      tp->end.offset,
						      tp);
	  tp = tp->end.tp;
	  continue;
	}

      if (loc->tp == tp && loc->offset <= next_part->start.offset)
	{
	  offset += loc->offset - current;
	  break;
	}
      
      tp = next_part;
      offset += (next_part->start.offset - current);
      next_part = tp_get_first_part(tp);
      current = 0;
    }

  D_RETURN_(offset);
}


pcapnav_result_t
libnd_tpm_map_offset_to_loc(const LND_TPM *tpm, off_t offset, LND_TraceLoc *loc)
{
  LND_TracePart    *tp, *next_part;
  off_t             current;
  pcapnav_t        *pcn;
  pcapnav_result_t  result;

  D_ENTER;

  if (!tpm || !loc)
    D_RETURN_(PCAPNAV_ERROR);

  tp = tpm->base;
  current = 0;
  next_part = tp_get_first_part(tp);

  while (tp)
    {      
      if (! next_part)
	{
	  /* This is a "plateau" -- check if our offset is within
	   * the plateau, otherwise fall off the end.
	   */
	  D(("Plateau, seeking %lu, size is %lu\n",
	     (long unsigned) (current + offset),
	     (long unsigned) tp->size));

	  /* As long as the required offset is within the plateau,
	   * use it. Otherwise, fall off the end (i.e., don't break).
	   */
	  if (current + offset < tp->size)	    {
	      offset = current + offset;
	      break;
	    }

	  /* Special case for the base trace -- don't fall of that end! */
	  if (! tp->end.tp && (current + offset) == tp->size)
	    {
	      offset = tp->size;
	      break;
	    }

	  offset -= tp->size - current;
	  current = tp->end.offset;
	  next_part = libnd_tp_find_part_after_offset(tp->end.tp,
						      tp->end.offset,
						      tp);

	  if (tp->start.offset == tp->end.offset)
	    {
	      D(("Special case -- empty parent part.\n"));
	      tp = tp->end.tp;
	      break;
	    }

	  tp = tp->end.tp;

	  D(("Down to part %p at %lu, remaining offset %lu\n",
	     tp, (long unsigned) current,
	     (long unsigned) offset));

	  D_ASSERT_PTR(tp);
	  continue;
	}

      if (current + offset < next_part->start.offset)
	{
	  offset = current + offset;
	  break;
	}

      tp = next_part;
      offset -= (next_part->start.offset - current);
      current = 0;
      next_part = tp_get_first_part(tp);
      D(("Up to part %p at %lu, remaining offset %lu\n",
	 tp, (long unsigned) tp->start.offset, (long unsigned) offset));
    }

  D(("Looking for offset %lu in part %p (size %lu, file %s)\n",
     (long unsigned) offset, tp, (long unsigned) tp->size,
     tp->in_filename));

  /* This was just an offset calculation -- now find the precise
   * start of the packet around offset.
   */
  if (! (pcn = pcapnav_open_offline(tp->in_filename)))
    {
      D(("Could not open %p's input file %s\n", tp, tp->in_filename));
      D_RETURN_(PCAPNAV_ERROR);
    }
  
  result = pcapnav_goto_offset(pcn, offset, PCAPNAV_CMP_ANY);
  if (result != PCAPNAV_DEFINITELY &&
      result != PCAPNAV_PERHAPS)    
    {
      D(("Finding offset failed\n"));
      pcapnav_close(pcn);
      D_RETURN_(result);
    }

  loc->tp     = tp;
  loc->offset = pcapnav_get_offset(pcn);
  pcapnav_close(pcn);

  D(("Resulting part is %p, offset: %lu\n", tp, (long unsigned) loc->offset));
  D_RETURN_(result);
}


gboolean         
libnd_tpm_map_loc_to_timestamp(LND_TPM *tpm,
				    LND_TraceLoc *loc,
				    struct bpf_timeval *tv)
{
  pcapnav_t *pcn;
  pcapnav_result_t pcn_result;
  gboolean result;

  D_ENTER;
  
  if (!tpm || !loc || !tv)
    D_RETURN_(FALSE);
  
  /* This was just an offset calculation -- now find the precise
   * start of the packet around offset.
   */
  if (! (pcn = pcapnav_open_offline(loc->tp->in_filename)))
    {
      D(("Could not open %p's input file %s\n", loc->tp, loc->tp->in_filename));
      D_RETURN_(FALSE);
    }
  
  pcn_result = pcapnav_goto_offset(pcn, loc->offset, PCAPNAV_CMP_ANY);
  if (pcn_result != PCAPNAV_DEFINITELY &&
      pcn_result != PCAPNAV_PERHAPS)    
    {
      D(("Finding offset failed\n"));
      pcapnav_close(pcn);
      D_RETURN_(FALSE);
    }
  
  result = pcapnav_get_current_timestamp(pcn, tv);
  pcapnav_close(pcn);

  D_RETURN_(result);
}


pcapnav_result_t
libnd_tpm_map_fraction_to_loc(const LND_TPM *tpm, double fraction, LND_TraceLoc *loc)
{
  off_t offset;
  pcapnav_result_t result;

  D_ENTER;

  if (!tpm || !loc)
    {
      memset(loc, 0, sizeof(LND_TraceLoc));
      D_RETURN_(PCAPNAV_ERROR);
    }

  if (fraction > 1.0)
    fraction = 1.0;
  if (fraction < 0.0)
    fraction = 0.0;
  
  /* Calculate the offset to jump to. pcapnav offsets start at 0
   * for the first packet, so there's no need to take care of the
   * file header.
   */
  offset = ((double) (tpm->size)) * fraction;
  D(("Finding fraction %f of %lu --> offset %lu\n",
     fraction, (long unsigned) tpm->size,
     (long unsigned) offset));
  
  result = libnd_tpm_map_offset_to_loc(tpm, offset, loc);
  D_RETURN_(result);
}


pcapnav_result_t
libnd_tpm_map_timestamp_to_loc(const LND_TPM *tpm, struct bpf_timeval *timestamp, LND_TraceLoc *loc)
{
  struct bpf_timeval  tv, ts;
  LND_TracePart      *next_part;
  pcapnav_t          *pcn;
  pcapnav_result_t    result;

  D_ENTER;

  if (!tpm || !timestamp || !loc)
    {
      memset(loc, 0, sizeof(LND_TraceLoc));
      D_RETURN_(PCAPNAV_ERROR);
    }

  tv = *timestamp;

  if (pcapnav_timeval_cmp(&tv, &tpm->base->start_ts) < 0)
    tv = tpm->base->start_ts;
  if (pcapnav_timeval_cmp(&tpm->base->end_ts, &tv) < 0)
    tv = tpm->base->end_ts;

  ts.tv_sec = ts.tv_usec = 0;
  loc->tp = tpm->base;
  next_part = tp_get_first_part(loc->tp);
        
  while (loc->tp)
    {
      D(("loc->tp: %p, next part: %p\n", loc->tp, next_part));

      if (! next_part)
	{
	  if (pcapnav_timeval_cmp(&tv, &loc->tp->end_ts) <= 0)
	    break;

	  next_part = libnd_tp_find_part_after_offset(loc->tp->end.tp,
						      loc->tp->end.offset,
						      loc->tp);
	  loc->tp = loc->tp->end.tp;
	  continue;
	}

      if (pcapnav_timeval_cmp(&tv, &next_part->start_ts) < 0)
	break;

      loc->tp = next_part;
      next_part = tp_get_first_part(loc->tp);
    }

  D_ASSERT_PTR(loc->tp);

  if (! (pcn = pcapnav_open_offline(loc->tp->in_filename)))
    {
      D(("Could not open %p's input file %s\n", loc->tp, loc->tp->in_filename));
      D_RETURN_(PCAPNAV_ERROR);
    }

  result = pcapnav_goto_timestamp(pcn, &tv);
  if (result != PCAPNAV_DEFINITELY &&
      result != PCAPNAV_PERHAPS)
    {
      D(("Finding offset failed\n"));
      pcapnav_close(pcn);
      D_RETURN_(result);
    }

  loc->offset = pcapnav_get_offset(pcn);
  pcapnav_close(pcn);

  D(("Resulting part is %p, offset: %lu\n",
     loc->tp, (long unsigned) loc->offset));
  
  D_RETURN_(result);
}


off_t
libnd_tpm_get_offset(const LND_TPM *tpm)
{
  LND_TraceLoc loc;

  loc.tp     = tpm->current->start.tp;
  loc.offset = tpm->current->start.offset;

  return libnd_tpm_map_loc_to_offset(tpm, &loc);
}


double           
libnd_tpm_get_space_fraction(const LND_TPM *tpm, off_t offset)
{
  if (!tpm || !tpm->current)
    return -1;

  if (tpm->size == 0)
    return 0.0;

  return ((double) offset) / tpm->size;
}


double           
libnd_tpm_get_time_fraction(const LND_TPM *tpm, const struct bpf_timeval *tv)
{
  if (!tpm || !tpm->current)
    return -1;

  return pcapnav_get_time_fraction(tpm->base->pcn, tv);
}


double           
libnd_tpm_get_rel_size(const LND_TPM *tpm)
{
  if (!tpm || !tpm->current || !tpm->trace)
    return -1;

  if (tpm->size == 0)
    return 1.0;

  return tpm->current->size / (double) tpm->size;
}


LND_Packet      *
libnd_tpm_get_packets(LND_TPM *tpm)
{
  if (!tpm)
    return NULL;

  return tpm->current->pl;
}


LND_Packet      *
libnd_tpm_get_sel(LND_TPM *tpm)
{
  if (!tpm)
    return NULL;

  return tpm->current->sel.pl;
}


void
libnd_tpm_pcap_read_handler(u_char *data,
			    const struct pcap_pkthdr *hdr,
			    const u_char *pdata)
{
  LND_TracePart *tp = (LND_TracePart *) data;
  LND_Packet *packet;

  if (!tp)
    return;

  packet = libnd_packet_new(tp, hdr->caplen);
  libnd_packet_set_data(packet, hdr, pdata);

  if (tp->pl_end)
    {
      tp->pl_end->next = packet;
      packet->prev = tp->pl_end;
      tp->pl_end = packet;
    }
  else
    {
      tp->pl = tp->pl_end = packet;
    }

  tp->num_packets++;
  tp->end_ts = hdr->ts;
  tp->size += pcapnav_get_pkthdr_size(tp->pcn) + hdr->caplen;
}


gboolean
libnd_tpm_find_locs(const LND_TPM *tpm,
		    LND_TraceArea *area,
		    LND_TraceLoc *start_loc,
		    LND_TraceLoc *end_loc)
{
  pcapnav_result_t result;

  D_ENTER;

  if (!tpm)
    D_RETURN_(FALSE);

  if (!area)
    {
      D(("Using entire trace.\n"));
      result = libnd_tpm_map_fraction_to_loc(tpm, 0, start_loc);
      if (result != PCAPNAV_DEFINITELY && result != PCAPNAV_PERHAPS)
	D_RETURN_(FALSE);

      result = libnd_tpm_map_fraction_to_loc(tpm, 1, end_loc);
      if (result != PCAPNAV_DEFINITELY && result != PCAPNAV_PERHAPS)
	D_RETURN_(FALSE);

      D_RETURN_(TRUE);
    }

  if (area->mode == LND_TPM_TIME)
    {      
      D(("Time area: %lu.%lu -- %lu.%lu\n",
	 area->area_time_start.tv_sec,
	 area->area_time_start.tv_usec,
	 area->area_time_end.tv_sec,
	 area->area_time_end.tv_usec));
	        
      result = libnd_tpm_map_timestamp_to_loc(tpm, &area->area_time_start, start_loc);
      if (result != PCAPNAV_DEFINITELY && result != PCAPNAV_PERHAPS)
	D_RETURN_(FALSE);

      result = libnd_tpm_map_timestamp_to_loc(tpm, &area->area_time_end, end_loc);
      if (result != PCAPNAV_DEFINITELY && result != PCAPNAV_PERHAPS)
	D_RETURN_(FALSE);
    }
  else
    {
      pcapnav_result_t result1, result2;
      D(("Space area: %f -- %f\n",
	 area->area_space_start, area->area_space_end));

      result1 = libnd_tpm_map_fraction_to_loc(tpm, area->area_space_start, start_loc);
      result2 = libnd_tpm_map_fraction_to_loc(tpm, area->area_space_end, end_loc);
      
      if (result1 != PCAPNAV_DEFINITELY || result2 != PCAPNAV_DEFINITELY)
	D_RETURN_(FALSE);
    }    
  
  D_RETURN_(TRUE);
}