/* doscan - Denial Of Service Capable Auditing of Networks
 * Copyright (C) 2003, 2005 Florian Weimer
 *
 * 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
 */

/* Implementation notes
 *
 * We use a table of mask/multiplier pairs (see 'multipliers' below)
 * to implement prefix-specific PRNGs.  A linear congruential
 * generator (LCG) is used, with the specified multiplier, the
 * additive constant 1, and a modulus which is one larger than the
 * specified width.  If the multiplier m and the modulus are
 * relatively prime, and m % 4 is 1, then the generator has maximum
 * period, and we scan the whole subnet.
 *
 * The multipliers given below were not chosen to suit the usual needs
 * of PRNGs, but we expected that this is sufficient to distribute the
 * load across the network. */

#include "config.h"
#include "ipv4.h"
#include "opt.h"
#include "subnets.h"

#include <cerrno>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

typedef struct {
  unsigned multiplier;
  unsigned mask;
} multiplier_t;

// The majority of the multipliers in the table below are NOT random,
// they were chosen after running a spectral test on the corresponding
// LCGs.

static multiplier_t multipliers[33] = {
  {0, 0},                       /*  0 */
  {0, 0},                       /*  1 */
  {0, 0},                       /*  2 */
  {0, 0},                       /*  3 */
  {0, 0},                       /*  4 */
  {0, 0},                       /*  5 */
  {0, 0},                       /*  6 */
  {0, 0},                       /*  7 */
  {8000261, 0x0FFFFF},          /*  8 */
  {4000237, 0x07FFFF},          /*  9 */
  {2000221, 0x03FFFF},          /* 10 */
  {1000069, 0x01FFFF},          /* 11 */
  {521093, 0x0FFFFF},           /* 12 */
  {261033, 0x07FFFF},           /* 13 */
  {131301, 0x03FFFF},           /* 14 */
  {101101, 0x01FFFF},           /* 15 */
  {31445, 0xFFFF},              /* 16 */
  {16149, 0x7FFF},              /* 17 */
  {8093, 0x3FFF},               /* 18 */
  {4173, 0x1FFF},               /* 19 */
  {2173, 0x0FFF},               /* 20 */
  {1197, 0x07FF},               /* 21 */
  {501, 0x03FF},                /* 22 */
  {261, 0X01FF},                /* 23 */
  {137, 0xFF},                  /* 24 */
  {97, 0x7F},                   /* 25 */
  {53, 0x3F},                   /* 26 */
  {25, 0x1F},                   /* 27 */
  {9, 0xF},                     /* 28 */
  {1, 0x7},                     /* 29 */
  {1, 0x3},                     /* 30 */
  {1, 0x1},                     /* 31 */
  {1, 0x0},                     /* 32 */
};

subnets::subnets()
  : current_address(0), next_prefix(prefixes.end()), next_address(0),
    processed(0), total(0)
{
}

bool
subnets::add(const char *s)
{
  unsigned mask;

  ipv4_prefix_t subnet;

  if (!ipv4_string_to_prefix(s, &subnet)) {
    if (!ipv4_string_to_address(s, &subnet.network)) {
      fprintf (stderr, "%s: illegal prefix '%s'\n",
               opt_program, s);
      return false;
    } else {
      // Address without prefix length, assume 32.
      subnet.length = 32;
    }
  }

  if (multipliers[subnet.length].multiplier == 0) {
    fprintf (stderr, "%s: prefix length %d in '%s' not supported\n",
             opt_program, subnet.length, s);
    return false;
  }

  mask = multipliers[subnet.length].mask;
  if (subnet.network & mask) {
    fprintf (stderr, "%s: length of prefix %s is too short\n",
             opt_program, s);
    return false;
  }


  if (subnet.network < 0x01000000) {
    fprintf (stderr, "%s: prefix %s with network zero not supported\n",
             opt_program, s);
    return false;
  }

  if ((total + mask + 1) <= total) {
    fprintf (stderr, "%s: sorry, cannot scan this many hosts\n",
             opt_program);
    return false;
  }

  prefixes.push_back(subnet);
  update_next_prefix();
  total += mask + 1;

  return true;
}

void
subnets::update_next_prefix()
{
  next_prefix = prefixes.begin();
  if (next_prefix != prefixes.end()) {
    next_address = next_prefix->network;
  } else {
    next_address = 0;
  }
}

void
subnets::add(char ** s, unsigned count)
{
  unsigned j;
  bool errors = false;

  for (j = 0; j < count; j++) {
    if (!add(s[j])) {
      errors = true;
    }
  }
  if (errors) {
    exit (EXIT_FAILURE);
  }
}

void
subnets::add_file(const char *name)
{
  FILE* file = fopen(name, "r");

  if (file == 0) {
    fprintf(stderr, "%s: failed to open, error was: %s\n",
            name, strerror(errno));
    exit(EXIT_FAILURE);
  }

  bool errors = false;
  while (!feof(file)) {
    char buf[30];

    if (fgets(buf, sizeof(buf), file)) {
      size_t len = strlen(buf);
      if (len == sizeof(buf) - 1) {
        fprintf(stderr, "%s: line too long\n", name);
        exit(EXIT_FAILURE);
      }

      if (!add(buf)) {
        errors = true;
      }
    } else {
      if (!feof(file)) {
        fprintf(stderr, "%s: cannot read from file\n", name);
        exit(EXIT_FAILURE);
      }
    }
  }
  if (errors) {
    exit (EXIT_FAILURE);
  }

  fclose(file);
}

void
subnets::shuffle()
{
  random_shuffle(prefixes.begin(), prefixes.end());
  update_next_prefix();
}

bool
subnets::finished(void)
{
  compute_next_address();
  return next_address == 0;
}

ipv4_t
subnets::next()
{
  // Updates next_address as a side effect.
  if (finished()) {
    abort();
  }

  show_progress ();
  current_address = next_address;
  next_address = 0;
  processed++;

  return current_address;
}

void
subnets::compute_next_address (void)
{
  ipv4_t network;
  unsigned host_offset, length;

  if (next_address != 0) {
    return;
  }

  if (next_prefix == prefixes.end()) {
    return;
  }

  network = next_prefix->network;
  length = next_prefix->length;
  host_offset = current_address - network;

  /* Next LCG iteration. */
  host_offset = (host_offset * multipliers[length].multiplier + 1) & multipliers[length].mask;

  if (host_offset == 0) {
    // We are at the end of this prefix.  Switch to the next prefix.
    next_prefix++;

    if (next_prefix != prefixes.end()) {
      next_address = next_prefix->network;
    } else {
      next_address = 0;
    }

  } else {
    next_address = network + host_offset;
  }
}

void
subnets::show_progress()
{
  if (! opt_verbose) {
    return;
  }

  /* Not a new prefix. */
  if ((current_address & ~multipliers[next_prefix->length].mask)
      == next_prefix->network) {
    return;
  }

  if (opt_verbose) {
    ipv4_string_t p;
    static int first = 1;
    int linefeed;

    linefeed = (! first) && opt_indicator;
    first = 0;

    ipv4_prefix_to_string (&*next_prefix, p);
    fprintf (stderr, "%s%s: about to scan %s\n",
             linefeed ? "\n" : "", opt_program, p);
    fflush (stderr);
  }
}

// arch-tag: 8d878b32-e911-42a9-b645-8b66c584cf10