/* $Id: compare.c,v 1.4 2006/03/03 17:27:38 bhockney Exp $ */

/* (C) 2004-2006 by Bob Hockney <zeus@ix.netcom.com>    *
 * Based on fwlogwatch written by                       *
 * Boris Wesslowski <Wesslowski@CERT.Uni-Stuttgart.DE>  *
 *                                                      *
 * sorting functions for wfwl_syslog                    *
 *                                                      *
 * This code is distributed under the terms of GNU GPL  */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include "compare.h"
#include "output.h"
#include "utils.h"

struct conn_data *first = NULL;
extern struct options opt;
extern struct field_order *fields;

/* compares two rows in data and indicates if they need to be sorted */
unsigned char compare(struct conn_data *op1, struct conn_data *op2)
{
  unsigned char cond = 0;
  int comp = 0;

  switch(opt.sortfield) {
  case SORT_ID:
    comp = strncmp(op1->filename, op2->filename, SHORTLEN);
    if (opt.sortmode == ORDER_ASCENDING) {
      if (comp > 0 || (comp == 0 && op1->linenum > op2->linenum)) cond++;
    } else {
      if (comp < 0 || (comp == 0 && op1->linenum < op2->linenum)) cond++;
    }
    break;
  case SORT_COUNT:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->count > op2->count) cond++;
    } else {
      if (op1->count < op2->count) cond++;
    }
    break;
  case SORT_START_TIME:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->start_time > op2->start_time) cond++;
    } else {
      if (op1->start_time < op2->start_time) cond++;
    }
    break;
  case SORT_END_TIME:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->end_time > op2->end_time) cond++;
    } else {
      if (op1->end_time < op2->end_time) cond++;
    }
    break;
  case SORT_DELTA_TIME:
    if (opt.sortmode == ORDER_ASCENDING) {
      if ((op1->end_time - op1->start_time) > (op2->end_time - op2->start_time)) cond++;
    } else {
      if ((op1->end_time - op1->start_time) < (op2->end_time - op2->start_time)) cond++;
    }
    break;
  case SORT_CHAINLABEL:
  case SORT_PREFIX: /* PREFIX vs CHAINLABEL */
    if (opt.sortmode == ORDER_ASCENDING) {
      if (strncmp(op1->log_label, op2->log_label, SHORTLEN) > 0) cond++;
    } else {
      if (strncmp(op1->log_label, op2->log_label, SHORTLEN) < 0) cond++;
    }
    break;
  case SORT_PROTOCOL:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->protocol > op2->protocol) cond++;
    } else {
      if (op1->protocol < op2->protocol) cond++;
    }
    break;
  case SORT_DATALEN:
  case SORT_IP_TOTLEN:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->datalen > op2->datalen) cond++;
    } else {
      if (op1->datalen < op2->datalen) cond++;
    }
    break;
  case SORT_SOURCEHOST:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (ntohl(op1->shost.s_addr) > ntohl(op2->shost.s_addr)) cond++;
    } else {
      if (ntohl(op1->shost.s_addr) < ntohl(op2->shost.s_addr)) cond++;
    }
    break;
  case SORT_SOURCEPORT:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->sport > op2->sport) cond++;
    } else {
      if (op1->sport < op2->sport) cond++;
    }
    break;
  case SORT_DESTHOST:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (ntohl(op1->dhost.s_addr) > ntohl(op2->dhost.s_addr)) cond++;
    } else {
      if (ntohl(op1->dhost.s_addr) < ntohl(op2->dhost.s_addr)) cond++;
    }
    break;
  case SORT_DESTPORT:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->dport > op2->dport) cond++;
    } else {
      if (op1->dport < op2->dport) cond++;
    }
    break;
  case SORT_ICMP_TYPE:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->icmp_type > op2->icmp_type) cond++;
    } else {
      if (op1->icmp_type < op2->icmp_type) cond++;
    }
    break;
  case SORT_ICMP_CODE:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->icmp_code > op2->icmp_code) cond++;
    } else {
      if (op1->icmp_code < op2->icmp_code) cond++;
    }
    break;
  case SORT_ICMP_ECHOID:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->icmp_echoid > op2->icmp_echoid) cond++;
    } else {
      if (op1->icmp_echoid < op2->icmp_echoid) cond++;
    }
    break;
  case SORT_ICMP_ECHOSEQ:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->icmp_echoseq > op2->icmp_echoseq) cond++;
    } else {
      if (op1->icmp_echoseq < op2->icmp_echoseq) cond++;
    }
    break;
  case SORT_ICMP_MTU:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->icmp_mtu > op2->icmp_mtu) cond++;
    } else {
      if (op1->icmp_mtu < op2->icmp_mtu) cond++;
    }
    break;
  case SORT_IP_ID:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->ipid > op2->ipid) cond++;
    } else {
      if (op1->ipid < op2->ipid) cond++;
    }
    break;
  case SORT_IP_IHL:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->ihl > op2->ihl) cond++;
    } else {
      if (op1->ihl < op2->ihl) cond++;
    }
    break;
  case SORT_IP_TOS:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->tos > op2->tos) cond++;
    } else {
      if (op1->tos < op2->tos) cond++;
    }
    break;
  case SORT_IP_TTL:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->ttl > op2->ttl) cond++;
    } else {
      if (op1->ttl < op2->ttl) cond++;
    }
    break;
  case SORT_LOCAL_HOST:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (strncmp(op1->hostname, op2->hostname, SHORTLEN) > 0) cond++;
    } else {
      if (strncmp(op1->hostname, op2->hostname, SHORTLEN) < 0) cond++;
    }
    break;
  case SORT_IN_IF:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (strncmp(op1->inif, op2->inif, SHORTLEN) > 0) cond++;
    } else {
      if (strncmp(op1->inif, op2->inif, SHORTLEN) < 0) cond++;
    }
    break;
  case SORT_OUT_IF:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (strncmp(op1->outif, op2->outif, SHORTLEN) > 0) cond++;
    } else {
      if (strncmp(op1->outif, op2->outif, SHORTLEN) < 0) cond++;
    }
    break;
  case SORT_FWMARK:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->fwmark > op2->fwmark) cond++;
    } else {
      if (op1->fwmark < op2->fwmark) cond++;
    }
    break;
  case SORT_MAC:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (strncmp(op1->raw_mac, op2->raw_mac, SHORTLEN) > 0) cond++;
    } else {
      if (strncmp(op1->raw_mac, op2->raw_mac, SHORTLEN) < 0) cond++;
    }
    break;
  case SORT_FRAGOFF:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->fragoff > op2->fragoff) cond++;
    } else {
      if (op1->fragoff < op2->fragoff) cond++;
    }
    break;
  case SORT_CSUM:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->csum > op2->csum) cond++;
    } else {
      if (op1->csum < op2->csum) cond++;
    }
    break;
  case SORT_TCP_SEQ:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->tcp_seq > op2->tcp_seq) cond++;
    } else {
      if (op1->tcp_seq < op2->tcp_seq) cond++;
    }
    break;
  case SORT_TCP_ACKSEQ:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->tcp_ack_seq > op2->tcp_ack_seq) cond++;
    } else {
      if (op1->tcp_ack_seq < op2->tcp_ack_seq) cond++;
    }
    break;
  case SORT_TCP_WINDOW:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->tcp_window > op2->tcp_window) cond++;
    } else {
      if (op1->tcp_window < op2->tcp_window) cond++;
    }
    break;
  case SORT_UDP_LEN:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->udp_len > op2->udp_len) cond++;
    } else {
      if (op1->udp_len < op2->udp_len) cond++;
    }
    break;
  case SORT_TCP_URGP:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->tcp_urgp > op2->tcp_urgp) cond++;
    } else {
      if (op1->tcp_urgp < op2->tcp_urgp) cond++;
    }
    break;
  case SORT_TCP_OPTS:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->flags > op2->flags) cond++;
    } else {
      if (op1->flags < op2->flags) cond++;
    }
    break;
  case SORT_AHESP_SPI:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->ahesp_spi > op2->ahesp_spi) cond++;
    } else {
      if (op1->ahesp_spi < op2->ahesp_spi) cond++;
    }
    break;
  case SORT_LOCAL_TIME:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (op1->local_time > op2->local_time) cond++;
    } else {
      if (op1->local_time < op2->local_time) cond++;
    }
    break;
  case SORT_ICMP_GW:
    if (opt.sortmode == ORDER_ASCENDING) {
      if (ntohl(op1->icmp_gw.s_addr) > ntohl(op2->icmp_gw.s_addr)) cond++;
    } else {
      if (ntohl(op1->icmp_gw.s_addr) < ntohl(op2->icmp_gw.s_addr)) cond++;
    }
    break;
  default:
    if (opt.verbose >= VERBOSE_INFO)
      fprintf(stderr, "Unrecognized sort key %i\n", opt.sortfield);
  }

  return cond;
}

/* sorts parsed data */
struct conn_data *wfwl_sort(struct conn_data *list) {
  struct conn_data *p, *q, *e, *tail;
  int size, merges, psize, qsize, i;

  if(list != NULL) {
    size = 1;
    while(1) {
      p = list;
      list = tail = NULL;
      merges = 0;
      while (p != NULL) {
        merges++;
        q = p;
        psize = 0;
        for (i = 0; i < size; i++) {
          psize++;
          q = q->next;
          if (q == NULL) break;
        }
        qsize = size;
        while (psize > 0 || ((qsize > 0) && (q != NULL))) {
          if (psize == 0) {
            e = q; q = q->next; qsize--;
          } else if (qsize == 0 || (q == NULL)) {
            e = p; p = p->next; psize--;
        /* compare function looks at struct opt to determine how to sort */
          } else if (compare(p,q) <= 0) {
            e = p; p = p->next; psize--;
          } else {
            e = q; q = q->next; qsize--;
          }
          if (tail != NULL) {
            tail->next = e;
          } else {
            list = e;
          }
          tail = e;
        } /* end "while (psize > 0 || ((qsize > 0) && (q != NULL)))" */
        p = q;
      } /* end "while (p != NULL)" */
      tail->next = NULL;
      if (merges <= 1)
        return list;
      size *= 2;
    } /* end "while(1)" */
  } else { /* end "while(list != NULL)" */
    return NULL;
  }
}