/* ***************************************************************** *
 * Copyright 1998 International Business Machines Corporation. All   *
 * Rights Reserved.                                                  *
 *                                                                   *
 * Please read this carefully.  Your use of this reference           *
 * implementation of certain of the IETF public-key infrastructure   *
 * specifications ("Software") indicates your acceptance of the      *
 * following.  If you do not agree to the following, do not install  *
 * or use any of the Software.                                       *
 *                                                                   *
 * Permission to use, reproduce, distribute and create derivative    *
 * works from the Software ("Software Derivative Works"), and to     *
 * distribute such Software Derivative Works is hereby granted to    *
 * you by International Business Machines Corporation ("IBM").  This *
 * permission includes a license under the patents of IBM that are   *
 * necessarily infringed by your use of the Software as provided by  *
 * IBM.                                                              *
 *                                                                   *
 * IBM licenses the Software to you on an "AS IS" basis, without     *
 * warranty of any kind.  IBM HEREBY EXPRESSLY DISCLAIMS ALL         *
 * WARRANTIES OR CONDITIONS, EITHER EXPRESS OR IMPLIED, INCLUDING,   *
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OR CONDITIONS OF       *
 * MERCHANTABILITY, NON INFRINGEMENT AND FITNESS FOR A PARTICULAR    *
 * PURPOSE.  You are solely responsible for determining the          *
 * appropriateness of using this Software and assume all risks       *
 * associated with the use of this Software, including but not       *
 * limited to the risks of program errors, damage to or loss of      *
 * data, programs or equipment, and unavailability or interruption   *
 * of operations.                                                    *
 *                                                                   *
 * IBM WILL NOT BE LIABLE FOR ANY DIRECT DAMAGES OR FOR ANY SPECIAL, *
 * INCIDENTAL, OR  INDIRECT DAMAGES OR FOR ANY ECONOMIC              *
 * CONSEQUENTIAL DAMAGES (INCLUDING LOST PROFITS OR SAVINGS), EVEN   *
 * IF IBM HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.  IBM  *
 * will not be liable for the loss of, or damage to, your records or *
 * data, or any damages claimed by you based on a third party claim. *
 *                                                                   *
 * IBM wishes to obtain your feedback to assist in improving the     *
 * Software.  You grant IBM a world-wide, royalty-free right to use, *
 * copy, distribute, sublicense and prepare derivative works based   *
 * upon any feedback, including materials, error corrections,        *
 * Software Derivatives, enhancements, suggestions and the like that *
 * you provide to IBM relating to the Software (this does not        *
 * include products for which you charge a royalty and distribute to *
 * IBM under other terms and conditions).                            *
 *                                                                   *
 * You agree to distribute the Software and any Software Derivatives *
 * under a license agreement that: 1) is sufficient to notify all    *
 * licensees of the Software and Software Derivatives that IBM       *
 * assumes no liability for any claim that may arise regarding the   *
 * Software or Software Derivatives, and 2) that disclaims all       *
 * warranties, both express and implied, from IBM regarding the      *
 * Software and Software Derivatives.  (If you include this          *
 * Agreement with any distribution of the Software or Software       *
 * Derivatives you will have met this requirement.)  You agree that  *
 * you will not delete any copyright notices in the Software.        *
 *                                                                   *
 * This Agreement is the exclusive statement of your rights in the   *
 * Software as provided by IBM.   Except for the rights granted to   *
 * you in the second paragraph above, You are not granted any other  *
 * patent rights, including but not limited to the right to make     *
 * combinations of the Software with products that infringe IBM      *
 * patents. You agree to comply with all applicable laws and         *
 * regulations, including all export and import laws and regulation. *
 * This Agreement is governed by the laws of the State of New York.  *
 * This Agreement supersedes all other communications,               *
 * understandings or agreements we may have had prior to this        *
 * Agreement.                                                        *
 * ***************************************************************** */

/*---------------------------------------------------------------------------------------*
 *
 * Terminology:
 * ------------
 *
 * Certification Path: list of n certificates, from 1 to n.
 *
 * 1  Certificates(S,I)   P(1)   E(1)
 * 2  Certificates(S,I)   P(2)   E(2)
 * 3  Certificates(S,I)   P(3)   E(3)
 * ...
 * d  Certificates(S,I)   P(d)   E(d)
 * ...
 * n  Certificates(S,I)   P(n)   E(n)
 * 
 * where:
 *
 * S = subject certificate
 * C = issuer certificate
 * P(1) = UNBOUNDED
 * E(1) = EMPTY
 * P(d) = Subject Certificate(d-1).NameConstraints.PermittedSubtrees
 * E(d) = Subject Certificate(d-1).NameConstraints.ExcludedSubtrees
 * and
 * P(j) = { p(1), p(2), ... , p(k) }, 
 *   where p(i) is a single GeneralSubtree permitted constraint
 * E(j) = { e(1), e(2), ... , e(k) }, 
 *   where e(i) is a single GeneralSubtree excluded constraint
 *
 * At depth d, there are d permitted subtrees and d excluded subtrees stored as state info.
 * At depth 1, the 1 permitted subtree is "UNBOUNDED" and the 1 excluded subtree is "EMPTY"
 *
 * At a given depth, we ask "is S permitted" and "is S excluded" for each name form S in 
 * subject certificate.
 *
 * Question:
 *    Is S permitted? : S must be permitted by P(1) and P(2) and P(3) and ... and P(d).
 *    Is S excluded?  : S must be excluded  by E(1) or  E(2) or  E(3) or  ... or  E(d).
 *
 * Next level question:
 *    Is S permitted by P(i), a given permitted name set?
 *    Is S excluded  by E(i), a given excluded  name set?
 *
 * Next level question:
 *    Is S permitted by p(1) or p(2) or p(3) or ... or p(k)
 *    Is S excluded  by e(1) or e(2) or e(3) or ... or e(k)
 *    where P(j) = { p(1), p(2), ..., p(k) }
 *    where E(j) = { e(1), e(2), ..., e(k) }
 *
 * Next level question:
 *    Is S permitted by p(j)?  
 *    API: bool is_permitted(GeneralName& name, GeneralName& constraint)
 *    Is S excluded  by e(j)?
 *    API: bool is_excluded(GeneralName& name, GeneralName& constraint)
 *
 * State information store as PermittedState and ExcludedState objects.
 * Classes need two APIs: 
 *  (1) one to query is a given name is permitted (or excluded)
 *  (2) the other to update the state with new set of permitted and excluded constraints
 *
 * usage: _permittedState.is_permitted(name)  and _permittedState.update(constraints)
 * usage:  _excludedState.is_excluded(name)   and  _excludedState.update(constraints)
 *
 *--------------------------------------------------------------------------------------*/


//------------------------------------------------------------
// includes
//------------------------------------------------------------

#include "functiontrace.h"
#include "chardefs.h"
#include "extrachardefs.h"   // TO DO: move these into chardefs.h
#include "jonahtpmsg.h"
#include "tpexception.h"
#include "pkixnameconstraints.h"
#include "tpdefines.h"


//------------------------------------------------------------
// private utility routines
//------------------------------------------------------------

static bool is_permitted  (GeneralName& name, ConstraintList* head);
static bool is_excluded   (GeneralName& name, ConstraintList* head);
static bool is_permitted  (GeneralName& name, GeneralSubtrees& constraints);
static bool is_excluded   (GeneralName& name, GeneralSubtrees& constraints);
static bool is_permitted  (GeneralName& name, GeneralName& constraint);
static bool is_excluded   (GeneralName& name, GeneralName& constraint);
static bool pattern_match (GeneralName& name, GeneralName& constraint);
static bool match_uri     (asn_ia5String& name, asn_ia5String& constraint);
static bool match_dNS     (asn_ia5String& name, asn_ia5String& constraint);
static bool match_rfc822  (asn_ia5String&  name, asn_ia5String&  constraint);
static bool match_uri     (const buffer_t& name, const buffer_t& constraint);
static bool match_dNS     (const buffer_t& name, const buffer_t& constraint);
static bool match_rfc822  (const buffer_t& name, const buffer_t& constraint);
static bool match_dn      (asn_x500name& name, asn_x500name& constraint);
static bool match_pattern (const buffer_t& name, const buffer_t& constraint);
static bool match_end     (const unsigned char* name, const unsigned char* constraint, int length);


// class ConstraintList

//------------------------------------------------------------
// method: ConstraintList 
//------------------------------------------------------------

ConstraintList::ConstraintList(GeneralSubtrees& constraints) 
: _next(0),
  _constraints()
{
   TPTRACE(jonahtp_trace_info, "ConstraintList::ConstraintList(GeneralSubtrees&)");

   int status = 0;

   buffer_t copyBuffer;

   //------------------------------------------------------------
   // This is a little tricky: parameter "constraints" comes from
   // accessing fields permittedSubtrees and excludedSubtrees of 
   // nameConstraints extension.  These structures have context-specific, 
   // implicit [0] and [1] tagging.  When we copy the subtrees here, 
   // we need to revert to UNIVERAL tagging and then reapply 
   // tagging when done copying.
   //------------------------------------------------------------

   int originalTag   = constraints.get_tag();
   int originalClass = constraints.get_class();

   constraints.set_tag(16);
   constraints.set_class(CLASS_UNIVERSAL);

   if ((status = constraints.write(copyBuffer)) != 0)
   {
      // be polite and undo tag mucking
      constraints.set_tag(originalTag);  
      constraints.set_class(originalClass);
      throw TPASNException(status);
   }

   if ((status = _constraints.read(copyBuffer)) != 0)
   {
      // be polite and undo tag mucking
      constraints.set_tag(originalTag);
      constraints.set_class(originalClass);
      throw TPASNException(status);
   }

   constraints.set_tag(originalTag);
   constraints.set_class(originalClass);
}


//------------------------------------------------------------
// method: ~ConstraintList 
//------------------------------------------------------------

ConstraintList::~ConstraintList()
{
   TPTRACE(jonahtp_trace_info, "ConstraintList::~ConstraintList()");
}


// class NameState

//------------------------------------------------------------
// method: NameState 
//------------------------------------------------------------

NameState::NameState()
: _head(0)
{
   TPTRACE(jonahtp_trace_info, "NameState::NameState()");
}


//------------------------------------------------------------
// method: ~NameState 
//------------------------------------------------------------

NameState::~NameState()
{
   TPTRACE(jonahtp_trace_info, "NameState::~NameState()");

   ConstraintList* p;

   if (_head)
   {
      // delete next item after head
      while (_head->_next)
      {
         if ((p = _head->_next) != 0)
         {
            _head->_next = p->_next;
            delete p;
         }
      }
      delete _head; 
      _head = 0;
   }
}


//------------------------------------------------------------
// method: update 
//------------------------------------------------------------

void 
NameState::update(GeneralSubtrees& permittedConstraints)
{
   TPTRACE(jonahtp_trace_info, "void NameState::update(GeneralSubtrees&)");

   ConstraintList* node = new ConstraintList(permittedConstraints);

   // update linked list

   if (_head)
   {
		node->_next = _head;
		_head = node;
   }
   else
   {
		_head = node;
   }
}


// subclass PermittedState

//------------------------------------------------------------
// method: is_permitted 
//------------------------------------------------------------

bool 
PermittedState::is_permitted(GeneralNames& names) 
{
   TPTRACE(jonahtp_trace_info, "bool PermittedState::is_permitted(GeneralNames&)");

   // not permitted if any one not permitted

   for (int i = 0; i < names.get_child_count(); i++)
   {
      if ( !is_permitted( *names[i] ) )
         return false;
   }

   // permitted by all

   return true;
}


//------------------------------------------------------------
// method: is_permitted 
//------------------------------------------------------------

bool 
PermittedState::is_permitted(GeneralName& name) 
{
   TPTRACE(jonahtp_trace_info, "PermittedState::is_permitted(GeneralName&)");

   return ::is_permitted(name, _head); 
}


//------------------------------------------------------------
// method: update 
//------------------------------------------------------------

void 
PermittedState::update(GeneralSubtrees& permittedConstraints)
{
   TPTRACE(jonahtp_trace_info, "void PermittedState::update(GeneralSubtrees&)");

   NameState::update(permittedConstraints);
}


// subclass ExcludedState

//------------------------------------------------------------
// method: is_excluded 
//------------------------------------------------------------

bool 
ExcludedState::is_excluded(GeneralNames& names) 
{
   TPTRACE(jonahtp_trace_info, "bool ExcludedState::is_excluded(GeneralNames&)");

   // excluded if any one is excluded

   for (int i = 0; i < names.get_child_count(); i++)
   {
      if ( is_excluded( *names[i] ) )
         return true;
   }

   // excluded by none

   return false;
}


//------------------------------------------------------------
// method: is_excluded 
//------------------------------------------------------------

bool 
ExcludedState::is_excluded(GeneralName& name) 
{
   TPTRACE(jonahtp_trace_info, "bool ExcludedState::is_excluded(GeneralName&)");

   return ::is_excluded(name, _head); 
}


//------------------------------------------------------------
// method: update 
//------------------------------------------------------------

void 
ExcludedState::update(GeneralSubtrees& excludedConstraints)
{
   TPTRACE(jonahtp_trace_info, "void ExcludedState::update(GeneralSubtrees&)");

   NameState::update(excludedConstraints);
}


// private utility functions

//------------------------------------------------------------
// method: is_permitted 
//------------------------------------------------------------

bool 
is_permitted(GeneralName& name, ConstraintList* head)
{
   TPTRACE(jonahtp_trace_info, "bool is_permitted(GeneralName&,ConstraintList*)");

   ConstraintList* next = head;

   // head = NULL is special case, means UNBOUNDED, any name permitted

   while (next)
   {
      // is S permitted? : S permitted by P(1) and P(2) and P(3) and ... and P(d)

      if ( !is_permitted(name, next->_constraints) )
         return false;

      next = next->_next;
   }

   // permitted by each permitted set

   return true;
}


//------------------------------------------------------------
// method: is_excluded 
//------------------------------------------------------------

bool 
is_excluded(GeneralName& name, ConstraintList* head)
{
   TPTRACE(jonahtp_trace_info, "bool is_excluded(GeneralName&,ConstraintList*)");

   ConstraintList* next = head;
   
   // head = NULL is special case, means EMPTY, no name excluded

   while (next)
   {
      // is S excluded? : S excluded by E(1) or E(2) or E(3) or ... or E(d)

      if ( is_excluded(name, next->_constraints) )
         return true;

      next = next->_next;
   }

   // not excluded by any excluded set

   return false;
}


//------------------------------------------------------------
// method: is_permitted 
//------------------------------------------------------------

bool 
is_permitted(GeneralName& name, GeneralSubtrees& constraints)
{
   TPTRACE(jonahtp_trace_info, "bool is_permitted(GeneralName&,GeneralSubtrees&)");

   // permitted if permitted by any constraint

   for (int i = 0; i < constraints.get_child_count(); i++)
   {
      if ( is_permitted(name, constraints[i]->base) )
         return true;
   }

   // not permitted by any constraint

   return false;
}


//------------------------------------------------------------
// method: is_excluded 
//------------------------------------------------------------

bool 
is_excluded(GeneralName& name, GeneralSubtrees& constraints)
{
   TPTRACE(jonahtp_trace_info, "bool is_excluded(GeneralName&,GeneralSubtrees&)");

   // excluded if excluded by any constraint

   for (int i = 0; i < constraints.get_child_count(); i++)
   {
      if ( is_excluded(name, constraints[i]->base) )
         return true;
   }

   // not excluded by any constraint

   return false;
}


//------------------------------------------------------------
// method: is_permitted 
//------------------------------------------------------------

bool 
is_permitted(GeneralName& name, GeneralName& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool is_permitted(GeneralName&,GeneralName&)");

   if ( name.selected() != constraint.selected() ) return true;
   if ( pattern_match(name, constraint) )          return true;
   return false;
}


//------------------------------------------------------------
// method: is_excluded 
//------------------------------------------------------------

bool 
is_excluded(GeneralName& name, GeneralName& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool is_excluded(GeneralName&,GeneralName&)");

   if ( name.selected() != constraint.selected() ) return false;
   if ( pattern_match(name, constraint) )          return true;
   return false;
}


//------------------------------------------------------------
// method: pattern_match 
//------------------------------------------------------------

bool
pattern_match(GeneralName& name, GeneralName& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool pattern_match(GeneralName&,GeneralName&)");

   int type = name.selected();

   switch (type)
   {
   case TYPE_rfc822Name:
      return match_rfc822(name.rfc822Name, constraint.rfc822Name);
      break;
   case TYPE_dNSName:
      return match_dNS(name.dNSName, constraint.dNSName);
      break;
   case TYPE_directoryname:
      return match_dn(name.directoryname, constraint.directoryname);
      break;
   case TYPE_uniformResourceIdentifier:
      return match_uri(name.uniformResourceIdentifier, constraint.uniformResourceIdentifier);
      break;
   }
   throw TPException(TP_NAME_CONSTRAINT_UNSUPPPORTED_NAME_FORM);
   return false;
}


//------------------------------------------------------------
// method: match_rfc822 
//------------------------------------------------------------

bool
match_rfc822(asn_ia5String& name, asn_ia5String& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_rfc822(asn_ia5String&,asn_ia5String&");

   int status = 0;

   buffer_t nameBuffer;
   buffer_t constraintBuffer;

   if ((status = name.get_value_IA5(nameBuffer)) != 0)
      throw TPASNException(status);
   if ((status = constraint.get_value_IA5(constraintBuffer)) != 0)
      throw TPASNException(status);

   return match_rfc822(nameBuffer, constraintBuffer);
}


//------------------------------------------------------------
// method: match_rfc822 
//------------------------------------------------------------

bool
match_rfc822(const buffer_t& name, const buffer_t& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_rfc822(buffer_t&,buffer_t&)");

   bool constraintHasAtSign = false;
   unsigned i = 0, j = 0;

   while ((i < constraint.data_len) && (constraint.data[i] != IA5_ATSIGN)) i++;
   if ((i < constraint.data_len) && (constraint.data[i] == IA5_ATSIGN)) 
      constraintHasAtSign = true;

   if (constraintHasAtSign)
   {
      return match_pattern(name, constraint);
   } 
   else
   {
      while ((j < name.data_len) && (name.data[j] != IA5_ATSIGN)) j++;
      if (j == name.data_len)
         return false;
      j++;
      buffer_t host;
      while (j < name.data_len) host.append( name.data[j++] );
      return match_pattern(host, constraint);
   }
}


//------------------------------------------------------------
// method: match_dNS 
//------------------------------------------------------------

bool
match_dNS(asn_ia5String& name, asn_ia5String& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_dNS(asn_ia5String&,asn_ia5String&)");

   int status = 0;

   buffer_t nameBuffer;
   buffer_t constraintBuffer;

   if ((status = name.get_value_IA5(nameBuffer)) != 0)
      throw TPASNException(status);
   if ((status = constraint.get_value_IA5(constraintBuffer)) != 0)
      throw TPASNException(status);

   return match_dNS(nameBuffer, constraintBuffer);
}


//------------------------------------------------------------
// method: match_dNS 
//------------------------------------------------------------

bool 
match_dNS(const buffer_t& name, const buffer_t& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_dNS(buffer_t&,buffer_t&)");

   return match_pattern(name, constraint);
}


//------------------------------------------------------------
// method: match_dn 
//------------------------------------------------------------

bool
match_dn(asn_x500name& name, asn_x500name& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_dn(asn_x500name&,asn_x500name&)");

   if ( name.get_child_count() < constraint.get_child_count() )
      return false;
   for (int i = 0; i < constraint.get_child_count(); i++)
   {
      if ( name[i]->get_child_count() != constraint[i]->get_child_count() )
         return false;
      if ( *name[i] != *constraint[i])
         return false;
   }
   return true;
}


//------------------------------------------------------------
// method: match_uri 
//------------------------------------------------------------

bool
match_uri(asn_ia5String& name, asn_ia5String& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_uri(asn_ia5String&,asn_ia5String&)");

   int status = 0;

   buffer_t nameBuffer;
   buffer_t constraintBuffer;

   if ((status = name.get_value_IA5(nameBuffer)) != 0)
      throw TPASNException(status);
   if ((status = constraint.get_value_IA5(constraintBuffer)) != 0)
      throw TPASNException(status);

   return match_uri(nameBuffer, constraintBuffer);
}


//------------------------------------------------------------
// method: match_uri 
//------------------------------------------------------------

bool 
match_uri(const buffer_t& name, const buffer_t& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_uri(buffer_t&,buffer_t&)");

   //------------------------------------------------------------
   // TO DO: make compliant with RFCs to make host extraction
   //        better.  This handles this simplest cases only.  
   //------------------------------------------------------------

   buffer_t host;

   unsigned i = 0;
   while ( (i < name.data_len) && (name.data[i] != IA5_COLON) ) i++;
   i++;
   while ( (i < name.data_len) && (name.data[i] == IA5_SLASH) ) i++;
   while ( (i < name.data_len) && (name.data[i] != IA5_SLASH) && (name.data[i] != IA5_COLON) )
      host.append( name.data[i++] );
   if (host.data_len == 0)
      return false;
   return match_pattern(host, constraint);
}


//------------------------------------------------------------
// method: match_pattern 
//------------------------------------------------------------

bool 
match_pattern(const buffer_t& name, const buffer_t& constraint)
{
   TPTRACE(jonahtp_trace_info, "bool match_pattern(buffer_t&,buffer_t&)");

   if (IA5_PERIOD == constraint.data[0])
   {
      if (name.data_len <= constraint.data_len) return false;
      unsigned offset = name.data_len - constraint.data_len;
      return match_end(name.data+offset, constraint.data, constraint.data_len);
   }
   else
   {
      if (name.data_len != constraint.data_len) return false;
      return match_end(name.data, constraint.data, name.data_len);
   }
}


//------------------------------------------------------------
// method: match_end 
//------------------------------------------------------------

bool 
match_end(const unsigned char* name, const unsigned char* constraint, int length)
{
   TPTRACE(jonahtp_trace_info, "bool match_end(unsigned char*,unsigned char*,int)");

   for (int i = 0; i < length ; i++)
   {
      if (toupper_IA5(name[i]) != toupper_IA5(constraint[i])) return false;
   }
   return true;
}


//------------------------------------------------------------
// method: toupper_IA5 
//------------------------------------------------------------

unsigned char 
toupper_IA5(unsigned char c) 
{
   if ((c >= 0x61u) && (c <= 0x7au))      return c - 0x20;
   else if ((c >= 0xe0u) && (c <= 0xf6u)) return c - 0x20;
   else if ((c >= 0xf8u) && (c <= 0xfeu)) return c - 0x20;
   return c;
}
