/**********************************************************************
 * file:  sr_router.c
 * date:  Mon Feb 18 12:50:42 PST 2002
 * Contact: [email protected]
 *
 * Description:
 *
 * This file contains all the functions that interact directly
 * with the routing table, as well as the main entry method
 * for routing.
 *
 **********************************************************************/

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "sr_if.h"
#include "sr_rt.h"
#include "sr_router.h"
#include "sr_protocol.h"
#include "sr_arpcache.h"
#include "sr_utils.h"

/* function prototypes */
char *get_lpm(struct sr_instance *sr, uint32_t ip_dest);
void send_icmp_msg(struct sr_instance *sr, struct sr_packet *this_packet, uint8_t type, uint8_t code);

/*---------------------------------------------------------------------
 * Method: sr_init(void)
 * Scope:  Global
 *
 * Initialize the routing subsystem
 *
 *---------------------------------------------------------------------*/

void sr_init(struct sr_instance *sr)
{
  /* REQUIRES */
  assert(sr);

  /* Initialize cache and cache cleanup thread */
  sr_arpcache_init(&(sr->cache));

  pthread_attr_init(&(sr->attr));
  pthread_attr_setdetachstate(&(sr->attr), PTHREAD_CREATE_JOINABLE);
  pthread_attr_setscope(&(sr->attr), PTHREAD_SCOPE_SYSTEM);
  pthread_attr_setscope(&(sr->attr), PTHREAD_SCOPE_SYSTEM);
  pthread_t thread;

  pthread_create(&thread, &(sr->attr), sr_arpcache_timeout, sr);

  /* Add initialization code here! */

} /* -- sr_init -- */

/*---------------------------------------------------------------------
 * Method: sr_send_arpreply(struct sr_instance *sr, uint8_t *orig_pkt,
 *             unsigned int orig_len, struct sr_if *src_iface)
 * Scope:  Local
 *
 * Send an ARP reply packet in response to an ARP request for one of
 * the router's interfaces
 *---------------------------------------------------------------------*/
void sr_send_arpreply(struct sr_instance *sr, uint8_t *orig_pkt,
                      unsigned int orig_len, struct sr_if *src_iface)
{
  /* Allocate space for packet */
  unsigned int reply_len = sizeof(sr_ethernet_hdr_t) + sizeof(sr_arp_hdr_t);
  uint8_t *reply_pkt = (uint8_t *)malloc(reply_len);
  if (NULL == reply_pkt)
  {
    fprintf(stderr, "Failed to allocate space for ARP reply");
    return;
  }

  sr_ethernet_hdr_t *orig_ethhdr = (sr_ethernet_hdr_t *)orig_pkt;
  sr_arp_hdr_t *orig_arphdr =
      (sr_arp_hdr_t *)(orig_pkt + sizeof(sr_ethernet_hdr_t));

  sr_ethernet_hdr_t *reply_ethhdr = (sr_ethernet_hdr_t *)reply_pkt;
  sr_arp_hdr_t *reply_arphdr =
      (sr_arp_hdr_t *)(reply_pkt + sizeof(sr_ethernet_hdr_t));

  /* Populate Ethernet header */
  memcpy(reply_ethhdr->ether_dhost, orig_ethhdr->ether_shost, ETHER_ADDR_LEN);
  memcpy(reply_ethhdr->ether_shost, src_iface->addr, ETHER_ADDR_LEN);
  reply_ethhdr->ether_type = orig_ethhdr->ether_type;

  /* Populate ARP header */
  memcpy(reply_arphdr, orig_arphdr, sizeof(sr_arp_hdr_t));
  reply_arphdr->ar_hrd = orig_arphdr->ar_hrd;
  reply_arphdr->ar_pro = orig_arphdr->ar_pro;
  reply_arphdr->ar_hln = orig_arphdr->ar_hln;
  reply_arphdr->ar_pln = orig_arphdr->ar_pln;
  reply_arphdr->ar_op = htons(arp_op_reply);
  memcpy(reply_arphdr->ar_tha, orig_arphdr->ar_sha, ETHER_ADDR_LEN);
  reply_arphdr->ar_tip = orig_arphdr->ar_sip;
  memcpy(reply_arphdr->ar_sha, src_iface->addr, ETHER_ADDR_LEN);
  reply_arphdr->ar_sip = src_iface->ip;

  /* Send ARP reply */
  printf("Send ARP reply\n");
  print_hdrs(reply_pkt, reply_len);
  sr_send_packet(sr, reply_pkt, reply_len, src_iface->name);
  free(reply_pkt);
} /* -- sr_send_arpreply -- */

/*---------------------------------------------------------------------
 * Method: sr_send_arprequest(struct sr_instance *sr,
 *             struct sr_arpreq *req,i struct sr_if *out_iface)
 * Scope:  Local
 *
 * Send an ARP reply packet in response to an ARP request for one of
 * the router's interfaces
 *---------------------------------------------------------------------*/
void sr_send_arprequest(struct sr_instance *sr, struct sr_arpreq *req,
                        struct sr_if *out_iface)
{
  /* Allocate space for ARP request packet */
  unsigned int reqst_len = sizeof(sr_ethernet_hdr_t) + sizeof(sr_arp_hdr_t);
  uint8_t *reqst_pkt = (uint8_t *)malloc(reqst_len);
  if (NULL == reqst_pkt)
  {
    fprintf(stderr, "Failed to allocate space for ARP reply");
    return;
  }

  sr_ethernet_hdr_t *reqst_ethhdr = (sr_ethernet_hdr_t *)reqst_pkt;
  sr_arp_hdr_t *reqst_arphdr =
      (sr_arp_hdr_t *)(reqst_pkt + sizeof(sr_ethernet_hdr_t));

  /* Populate Ethernet header */
  memset(reqst_ethhdr->ether_dhost, 0xFF, ETHER_ADDR_LEN);
  memcpy(reqst_ethhdr->ether_shost, out_iface->addr, ETHER_ADDR_LEN);
  reqst_ethhdr->ether_type = htons(ethertype_arp);

  /* Populate ARP header */
  reqst_arphdr->ar_hrd = htons(arp_hrd_ethernet);
  reqst_arphdr->ar_pro = htons(ethertype_ip);
  reqst_arphdr->ar_hln = ETHER_ADDR_LEN;
  reqst_arphdr->ar_pln = sizeof(uint32_t);
  reqst_arphdr->ar_op = htons(arp_op_request);
  memcpy(reqst_arphdr->ar_sha, out_iface->addr, ETHER_ADDR_LEN);
  reqst_arphdr->ar_sip = out_iface->ip;
  memset(reqst_arphdr->ar_tha, 0x00, ETHER_ADDR_LEN);
  reqst_arphdr->ar_tip = req->ip;

  /* Send ARP request */
  printf("Send ARP request\n");
  print_hdrs(reqst_pkt, reqst_len);
  sr_send_packet(sr, reqst_pkt, reqst_len, out_iface->name);
  free(reqst_pkt);
} /* -- sr_send_arprequest -- */

/*---------------------------------------------------------------------
 * Method: sr_handle_arpreq(struct sr_instance *sr,
 *             struct sr_arpreq *req, struct sr_if *out_iface)
 * Scope:  Global
 *
 * Perform processing for a pending ARP request: do nothing, timeout, or
 * or generate an ARP request packet
 *---------------------------------------------------------------------*/
void sr_handle_arpreq(struct sr_instance *sr, struct sr_arpreq *req,
                      struct sr_if *out_iface)
{
  time_t now = time(NULL);
  if (difftime(now, req->sent) >= 1.0)
  {
    if (req->times_sent >= 5)
    {
      /*********************************************************************/
      /* TODO: send ICMP host uncreachable to the source address of all    */
      /* packets waiting on this request                                   */
      struct sr_packet *this_packet = req->packets;
      while (this_packet != NULL)
      {
        send_icmp_msg(sr, this_packet, 3, 0);
        this_packet = this_packet->next;
      }
      /*********************************************************************/

      sr_arpreq_destroy(&(sr->cache), req);
    }
    else
    {
      /* Send ARP request packet */
      sr_send_arprequest(sr, req, out_iface);

      /* Update ARP request entry to indicate ARP request packet was sent */
      req->sent = now;
      req->times_sent++;
    }
  }
} /* -- sr_handle_arpreq -- */

/*---------------------------------------------------------------------
 * Method: void sr_waitforarp(struct sr_instance *sr, uint8_t *pkt,
 *             unsigned int len, uint32_t next_hop_ip,
 *             struct sr_if *out_iface)
 * Scope:  Local
 *
 * Queue a packet to wait for an entry to be added to the ARP cache
 *---------------------------------------------------------------------*/
void sr_waitforarp(struct sr_instance *sr, uint8_t *pkt,
                   unsigned int len, uint32_t next_hop_ip, struct sr_if *out_iface)
{
  struct sr_arpreq *req = sr_arpcache_queuereq(&(sr->cache), next_hop_ip,
                                               pkt, len, out_iface->name);
  sr_handle_arpreq(sr, req, out_iface);
} /* -- sr_waitforarp -- */

/*---------------------------------------------------------------------
 * Method: sr_handlepacket_arp(struct sr_instance *sr, uint8_t *pkt,
 *             unsigned int len, struct sr_if *src_iface)
 * Scope:  Local
 *
 * Handle an ARP packet that was received by the router
 *---------------------------------------------------------------------*/
void sr_handlepacket_arp(struct sr_instance *sr, uint8_t *pkt,
                         unsigned int len, struct sr_if *src_iface)
{
  /* Drop packet if it is less than the size of Ethernet and ARP headers */
  if (len < (sizeof(sr_ethernet_hdr_t) + sizeof(sr_arp_hdr_t)))
  {
    printf("Packet is too short => drop packet\n");
    return;
  }

  sr_arp_hdr_t *arphdr = (sr_arp_hdr_t *)(pkt + sizeof(sr_ethernet_hdr_t));

  switch (ntohs(arphdr->ar_op))
  {
  case arp_op_request:
  {
    /* Check if request is for one of my interfaces */
    if (arphdr->ar_tip == src_iface->ip)
    {
      sr_send_arpreply(sr, pkt, len, src_iface);
    }
    break;
  }
  case arp_op_reply:
  {
    /* Check if reply is for one of my interfaces */
    if (arphdr->ar_tip != src_iface->ip)
    {
      break;
    }

    /* Update ARP cache with contents of ARP reply */
    struct sr_arpreq *req = sr_arpcache_insert(&(sr->cache), arphdr->ar_sha,
                                               arphdr->ar_sip);

    /* Process pending ARP request entry, if there is one */
    if (req != NULL)
    {
      /*********************************************************************/
      /* TODO: send all packets on the req->packets linked list            */
      struct sr_packet *this_packet = req->packets;
      sr_ethernet_hdr_t *arp_hdr = (sr_ethernet_hdr_t *)(pkt);
      while (this_packet != NULL) /* while there are more packets to handle */
      {
        sr_ethernet_hdr_t *this_ethernet = (sr_ethernet_hdr_t *)(this_packet->buf);
        memcpy(this_ethernet->ether_dhost, arp_hdr->ether_shost, sizeof(uint8_t) * ETHER_ADDR_LEN);
        memcpy(this_ethernet->ether_shost, arp_hdr->ether_dhost, sizeof(uint8_t) * ETHER_ADDR_LEN);
        sr_send_packet(sr, this_packet->buf, this_packet->len, this_packet->iface); /* sending packet */
        this_packet = this_packet->next;                                            /* setup to work on next packet */
      }
      /*********************************************************************/

      /* Release ARP request entry */
      sr_arpreq_destroy(&(sr->cache), req);
    }
    break;
  }
  default:
    printf("Unknown ARP opcode => drop packet\n");
    return;
  }
} /* -- sr_handlepacket_arp -- */

/*---------------------------------------------------------------------
 * Method: sr_handlepacket(uint8_t* p,char* interface)
 * Scope:  Global
 *
 * This method is called each time the router receives a packet on the
 * interface.  The packet buffer, the packet length and the receiving
 * interface are passed in as parameters. The packet is complete with
 * ethernet headers.
 *
 * Note: Both the packet buffer and the character's memory are handled
 * by sr_vns_comm.c that means do NOT delete either.  Make a copy of the
 * packet instead if you intend to keep it around beyond the scope of
 * the method call.
 *
 *---------------------------------------------------------------------*/

void sr_handlepacket(struct sr_instance *sr,
                     uint8_t *packet /* lent */,
                     unsigned int len,
                     char *interface /* lent */)
{
  /* REQUIRES */
  assert(sr);
  assert(packet);
  assert(interface);

  printf("*** -> Received packet of length %d \n", len);

  /*************************************************************************/
  /* TODO: Handle packets                                                  */
  uint16_t ethertype1 = ethertype(packet);
  struct sr_ethernet_hdr *ethernet_hdr = (struct sr_ethernet_hdr *)packet;

  /*---------------------------------------------------------------------*
  *  determine if it's a broadcast pracket or not                        *
  *---------------------------------------------------------------------*/
  int i;
  int is_bcast_pkt = 1;
  for (i = 0; i < ETHER_ADDR_LEN; i++)
  {
    /*---------------------------------------------------------------------*
     *      Check the destination host for desingated hex code 0xFF        *
     *      If it does have 0xFF in it then it is a broadcast packet       *
     *      If it doesn't, then it is not a broadcast packet               *
     *---------------------------------------------------------------------*/
    if (ethernet_hdr->ether_dhost[i] != 0xFF)
    {
      is_bcast_pkt = 0; /* didn't find 0xFF in destination host so its not a broadcast */
    }
  }

  int router_should_recieve_pkt = 0;
  sr_ip_hdr_t *dest = (sr_ip_hdr_t *)((sizeof(sr_ethernet_hdr_t)) + packet);
  struct sr_if *current_entry = sr->if_list;
  while (current_entry != NULL) /* while there is an entry to process */
  {
    if (current_entry->ip == dest->ip_dst) /* indicates the packet is indeed addressed to the router */
    {
      router_should_recieve_pkt = 1;
    }
    current_entry = current_entry->next; /* goes to next entry */
  }
  if (is_bcast_pkt) /* if it is a broadcast packet */
  {
    if (ethertype1 == ethertype_arp) /* and its arp */
    {
      sr_handlepacket_arp(sr, packet, len, sr_get_interface(sr, interface));
    }
    else /* broadcast but not arp */
    {
      fprintf(stderr, "Error, broadcast packet but not arp packet");
    }
  }
  else if (router_should_recieve_pkt) /* is addressed to router, but not arp */
  {
    if (ethertype1 == ethertype_ip) /* is IP */
    {
      if (dest->ip_p == ip_protocol_icmp) /* if it is an icmp packet */
      {
        sr_icmp_hdr_t *icmp_hdr = (sr_icmp_hdr_t *)(sizeof(sr_ip_hdr_t) + sizeof(sr_ethernet_hdr_t) + packet);
        if (icmp_hdr->icmp_type == 9) /* 9 = ICMP_ECHO_REQUEST */
        {
          struct sr_packet *this_packet = (struct sr_packet *)malloc(sizeof(struct sr_packet));
          this_packet->iface = interface;
          this_packet->len = len;
          this_packet->buf = packet;

          uint8_t *packet = (uint8_t *)malloc(sizeof(sr_icmp_hdr_t) + sizeof(sr_ip_hdr_t) + sizeof(sr_ethernet_hdr_t) + 60);

          sr_ethernet_hdr_t *ethernet_hdr = (sr_ethernet_hdr_t *)packet;
          sr_icmp_hdr_t *icmp_hdr = (sr_icmp_hdr_t *)(sizeof(sr_ip_hdr_t) + sizeof(sr_ethernet_hdr_t) + packet);
          sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(packet + sizeof(sr_ethernet_hdr_t));
          uint8_t *queued_packet = this_packet->buf;
          sr_ip_hdr_t *queued_hdr = (sr_ip_hdr_t *)(queued_packet + sizeof(sr_ethernet_hdr_t));
          sr_icmp_hdr_t *queued_icmp = (sr_icmp_hdr_t *)(queued_packet + sizeof(sr_ethernet_hdr_t) + sizeof(sr_ip_hdr_t));

          /*---------------------------------------------------------------------*
           *  Creation of the IP header                                          */
          ip_hdr->ip_hl = 5;
          ip_hdr->ip_len = 60 + sizeof(sr_icmp_hdr_t) + htons(sizeof(sr_ip_hdr_t));
          ip_hdr->ip_off = 0;
          ip_hdr->ip_id = 0;
          ip_hdr->ip_dst = queued_hdr->ip_src;
          ip_hdr->ip_v = 4;
          ip_hdr->ip_tos = 0;
          ip_hdr->ip_ttl = 128; /* restricted to same continent */
          ip_hdr->ip_sum = 0x0000;
          ip_hdr->ip_p = ip_protocol_icmp;

          char *outbound_iface = get_lpm(sr, htonl(ip_hdr->ip_dst));
          ip_hdr->ip_src = sr_get_interface(sr, outbound_iface)->ip;
          ip_hdr->ip_sum = cksum((uint8_t *)ip_hdr, 60 + sizeof(sr_icmp_hdr_t) + sizeof(sr_ip_hdr_t));
          /*  Done with creation of the IP header                                *
           *---------------------------------------------------------------------*/

          /*---------------------------------------------------------------------*
           *  Creation of the ethernet header                                    */
          sr_ethernet_hdr_t *queued_eth_hdr = (sr_ethernet_hdr_t *)(queued_packet);
          memcpy(ethernet_hdr->ether_dhost, queued_eth_hdr->ether_shost, sizeof(uint8_t) * ETHER_ADDR_LEN);
          memcpy(ethernet_hdr->ether_shost, sr_get_interface(sr, outbound_iface)->addr, sizeof(uint8_t) * ETHER_ADDR_LEN);
          ethernet_hdr->ether_type = htons(ethertype_ip);
          /*  Done with Creation of the ethernet header                          *
           *---------------------------------------------------------------------*/

          /*---------------------------------------------------------------------*
           *  Creation of the icmp header                                        */
          memcpy(icmp_hdr, queued_icmp, sizeof(sr_icmp_hdr_t) + 60);
          icmp_hdr->icmp_code = 0;
          icmp_hdr->icmp_type = 0;
          icmp_hdr->icmp_sum = 0x0000;
          icmp_hdr->icmp_sum = cksum((uint16_t *)icmp_hdr, sizeof(sr_icmp_hdr_t) + 60);
          /*  Done with creation of the icmp header                              *
           *---------------------------------------------------------------------*/

          /* actually send sthe packet */
          sr_send_packet(sr, packet, 60 + sizeof(sr_ethernet_hdr_t) + sizeof(sr_icmp_hdr_t)  + sizeof(sr_ip_hdr_t), outbound_iface);

          /* feeing up memory */
          free(this_packet);
          free(packet);
        }
      }
      else if (dest->ip_p == 6 || dest->ip_p == 17) /* TCP or UDP */
      {
        struct sr_packet *this_packet = (struct sr_packet *)malloc(sizeof(struct sr_packet));
        this_packet->iface = interface;
        this_packet->buf = packet;
        this_packet->len = len;
        send_icmp_msg(sr, this_packet, 3, 3);
        free(this_packet); /* feeing up memory */
      }
    }
    else
    {
      fprintf(stderr, "Error, Not IP packet");
    }
  }
  else
  {
    /*---------------------------------------------------------------------*
     *  Now we are going to forward the packet to the correct host         *
     *---------------------------------------------------------------------*/
    if (ethertype1 == ethertype_ip)
    {
      sr_ip_hdr_t *dest = (sr_ip_hdr_t *)((sizeof(sr_ethernet_hdr_t)) + packet);
      if (len < sizeof(sr_ip_hdr_t) + sizeof(sr_ethernet_hdr_t)) /* if less then minimum length */
      {
        fprintf(stderr, "Error, IP packet < minimum length\n");
        return;
      }

      /*---------------------------------------------------------------------*
       *  Calculate checksum and compare it to ensure packet integrity       *
       *---------------------------------------------------------------------*/
      if (cksum(dest, sizeof(sr_ip_hdr_t)) != 0xffff)
      {
        fprintf(stderr, "Error, checksum wrong, package integrity unverified, packet dropped\n");
        return;
      }
      dest->ip_ttl--;
      if (dest->ip_ttl == 0) /* time to live of packet = 0 */
      {
        struct sr_packet *this_packet = (struct sr_packet *)malloc(sizeof(struct sr_packet));
        this_packet->iface = interface;
        this_packet->buf = packet;
        this_packet->len = len;

        send_icmp_msg(sr, this_packet, 11, 0); /* code 11 = Destination Network Unreachable */
        return;
      }

      /*---------------------------------------------------------------------*
       *  Re-calculate checksum with newly found destination address         *
       *---------------------------------------------------------------------*/
      dest->ip_sum = 0x0000;
      dest->ip_sum = cksum(dest, sizeof(sr_ip_hdr_t));
      char *outbound_iface = get_lpm(sr, htonl(dest->ip_dst));
      if (outbound_iface == NULL) /* prefix matching couldn't find a match */
      {
        struct sr_packet *this_packet = (struct sr_packet *)malloc(sizeof(struct sr_packet));
        this_packet->iface = interface;
        this_packet->buf = packet;
        this_packet->len = len;
        send_icmp_msg(sr, this_packet, 3, 0); /* code 3 = Port Unreachable */
        return;
      }
      struct sr_arpentry *arpentry = sr_arpcache_lookup(&(sr->cache), dest->ip_dst);
      if (arpentry != NULL) /* found destination mac address in arpcache */
      {
        memcpy(ethernet_hdr->ether_dhost, arpentry->mac, ETHER_ADDR_LEN);
        memcpy(ethernet_hdr->ether_shost, (sr_get_interface(sr, outbound_iface)->addr), ETHER_ADDR_LEN);
        sr_send_packet(sr, packet, len, outbound_iface);
        free(arpentry);
      }
      else /* arpentry == NULL aka, destination mac address not found in arpcache */
      {
        sr_waitforarp(sr, packet, len, ntohl(htonl(dest->ip_dst)), sr_get_interface(sr, outbound_iface));
      }
    }
    else if (ethertype1 == ethertype_arp) /* if we are handling an arp packet */
    {
      sr_handlepacket_arp(sr, packet, len, sr_get_interface(sr, interface));
    }
    else /* neither IP nor ARP packet */
    {
      fprintf(stderr, "Error, packet neither IP nor ARP");
    }
  }
  /*************************************************************************/

} /* end sr_ForwardPacket */

void send_icmp_msg(struct sr_instance *sr, struct sr_packet *this_packet, uint8_t type, uint8_t code)
{
  int len = 8 + sizeof(sr_ip_hdr_t) + sizeof(sr_icmp_t3_hdr_t) + sizeof(sr_ethernet_hdr_t);
  uint8_t *packet = (uint8_t *)malloc(len);
  sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(sizeof(sr_ethernet_hdr_t) + packet);
  sr_icmp_t3_hdr_t *icmp_hdr = (sr_icmp_t3_hdr_t *)(sizeof(sr_ip_hdr_t) + sizeof(sr_ethernet_hdr_t) + packet);
  sr_ethernet_hdr_t *ethernet_hdr = (sr_ethernet_hdr_t *)packet;
  uint8_t *queued_packet = this_packet->buf;
  sr_ip_hdr_t *queued_hdr = (sr_ip_hdr_t *)(sizeof(sr_ethernet_hdr_t) + queued_packet);

  /*---------------------------------------------------------------------*
 *  create ip header                                                   *
 *---------------------------------------------------------------------*/
  ip_hdr->ip_hl = 5;
  ip_hdr->ip_v = 4;
  ip_hdr->ip_tos = 0;
  ip_hdr->ip_len = htons(sizeof(sr_icmp_t3_hdr_t) + sizeof(sr_ip_hdr_t));
  ip_hdr->ip_sum = 0x0000;
  ip_hdr->ip_id = 0;
  ip_hdr->ip_off = 0;
  ip_hdr->ip_ttl = 128; /* restricted to same continent */
  ip_hdr->ip_p = ip_protocol_icmp;
  ip_hdr->ip_dst = queued_hdr->ip_src;
  char *outbound_iface = get_lpm(sr, htonl(ip_hdr->ip_dst));
  ip_hdr->ip_src = sr_get_interface(sr, outbound_iface)->ip;
  ip_hdr->ip_sum = cksum((uint8_t *)ip_hdr, sizeof(sr_icmp_t3_hdr_t) + sizeof(sr_ip_hdr_t)); /* compute checksum for ip header */

  /*---------------------------------------------------------------------*
   *  create ethernet header                                             *
   *---------------------------------------------------------------------*/
  sr_ethernet_hdr_t *queued_eth_hdr = (sr_ethernet_hdr_t *)(queued_packet);
  memcpy(ethernet_hdr->ether_dhost, queued_eth_hdr->ether_shost, sizeof(uint8_t) * ETHER_ADDR_LEN);
  memcpy(ethernet_hdr->ether_shost, sr_get_interface(sr, outbound_iface)->addr, sizeof(uint8_t) * ETHER_ADDR_LEN);
  ethernet_hdr->ether_type = htons(ethertype_ip);
  sr_send_packet(sr, packet, len, outbound_iface);
  free(packet);

  /*---------------------------------------------------------------------*
 *  create icmp header                                                 *
 *---------------------------------------------------------------------*/
  memcpy(icmp_hdr->data, queued_hdr, 8 + sizeof(sr_icmp_hdr_t) + sizeof(sr_ip_hdr_t));
  icmp_hdr->icmp_sum = 0x0000;
  icmp_hdr->icmp_code = code;
  icmp_hdr->icmp_type = type;
  icmp_hdr->icmp_sum = cksum((uint16_t *)icmp_hdr, sizeof(sr_icmp_t3_hdr_t)); /* compute checksum for icmp header */
}

char *get_lpm(struct sr_instance *sr, uint32_t ip_dest) /* Longest Prefix Match */
{
  char *iface; /* interface we want to send */
  struct sr_rt *curr_entry = sr->routing_table;
  int highest_bits_matched = 0;
  while (curr_entry != NULL) /* while we have an entry to work with */
  {
    int bits_matched = 0;
    int i;
    for (i = 31; i >= 0; --i)
    {
      int ip_dest_bit = (ip_dest >> i) & 1;
      int curr_entry_bit = (htonl(*(uint32_t *)&curr_entry->dest) >> i) & 1;
      if (ip_dest_bit == curr_entry_bit)
      {
        bits_matched++;
      }
      else
      {
        break;
      }
    }
    if (bits_matched > highest_bits_matched)
    {
      highest_bits_matched = bits_matched;
      iface = curr_entry->interface;
    }
    curr_entry = curr_entry->next;
  }
  if (highest_bits_matched != 32)
  {
    return NULL;
  }
  return iface;
}