developer.intra2net.com Git - libi2ncommon/blob - src/timefunc.cpp

   1 /** @file
   2  * @brief time related functions.
   3  *
   4  * @copyright Copyright &copy; 2001-2008 by Intra2net AG
   5  * @license commercial
   6  * @contact info@intra2net.com
   7  *
   8  */
   9
  10
  11 #include <string>
  12 #include <sstream>
  13 #include <iostream>
  14 #include <iomanip>
  15 #include <bitset>
  16 #include <stdexcept>
  17 #include <iterator>
  18 #include <algorithm>
  19
  20 #include <time.h>
  21 #include <unistd.h>
  22 #include <string.h>
  23 #include <sys/timeb.h>
  24 #include <sys/syscall.h>
  25
  26 #include <timefunc.hxx>
  27 #include <i18n.h>
  28
  29
  30 // define missing POSIX.1b constants...
  31
  32 #ifndef CLOCK_REALTIME
  33 #define CLOCK_REALTIME 0
  34 #endif
  35 #ifndef CLOCK_MONOTONIC
  36 #define CLOCK_MONOTONIC 1
  37 #endif
  38
  39
  40
  41 using namespace std;
  42
  43 double prec_time(void)
  44 {
  45     struct timeb tb;
  46     double ret;
  47
  48     ftime(&tb);
  49
  50     ret=tb.time+(static_cast<float>(tb.millitm)/1000);
  51
  52     return ret;
  53 }
  54
  55 // converts ISO-DATE: 2003-06-13
  56 int date_to_seconds(const std::string &date)
  57 {
  58     int rtn = -1, year = -1, month = -1, day = -1;
  59
  60     string::size_type pos = date.find("-");
  61     if (pos == string::npos)
  62         return rtn;
  63
  64     istringstream in(string(date,0,pos));
  65     in >> year;
  66     year -= 1900;
  67
  68     string dstr(date, pos+1);
  69     if ((pos = dstr.find("-")) == string::npos)
  70         return rtn;
  71
  72     in.clear();
  73     in.str(string(dstr, 0, pos));
  74     in >> month;
  75     month -= 1;
  76
  77     in.clear();
  78     in.str(string(dstr, pos+1));
  79     in >> day;
  80
  81     if (year < 0 || month == -1 || day == -1)
  82         return rtn;
  83
  84     struct tm tm_struct;
  85     bzero (&tm_struct, sizeof(struct tm));
  86     tm_struct.tm_year = year;
  87     tm_struct.tm_mon = month;
  88     tm_struct.tm_mday = day;
  89     tm_struct.tm_isdst = -1;
  90
  91     rtn = mktime (&tm_struct);
  92     return rtn;
  93 }
  94
  95 string make_nice_time(int seconds)
  96 {
  97     ostringstream out;
  98
  99     int days=seconds/86400;
 100     seconds%=86400;
 101
 102     int hours=seconds/3600;
 103     seconds%=3600;
 104
 105     int minutes=seconds/60;
 106     seconds%=60;
 107
 108     if (days==1)
 109         out << i18n("1 day") << ", ";
 110     else if (days>1)
 111         out << days << ' ' << i18n("days") << ", ";
 112
 113     out << setfill('0');
 114     out << setw(2) << hours << ':' << setw(2) << minutes << ':' << setw(2) << seconds;
 115
 116     return out.str();
 117 }
 118
 119 string format_full_time(int seconds)
 120 {
 121     char buf[50];
 122     memset (buf, 0, 50);
 123     struct tm *ta = localtime ((time_t *)&seconds);
 124
 125     strftime (buf, 49, "%d.%m.%Y %H:%M", ta);
 126     return string(buf);
 127 }
 128
 129 void seconds_to_hour_minute(int seconds, int *hour, int *minute)
 130 {
 131     if (hour != NULL) {
 132         *hour = 0;
 133         while (seconds >= 3600) {
 134             seconds-=3600;
 135             (*hour)++;
 136         }
 137     }
 138
 139     if (minute != NULL) {
 140         *minute = 0;
 141         while (seconds >= 60) {
 142             seconds-=60;
 143             (*minute)++;
 144         }
 145     }
 146 }
 147
 148 std::string output_hour_minute(int hour, int minute, bool h_for_00)
 149 {
 150     ostringstream out;
 151
 152     if (hour >= 0 && hour < 10)
 153         out << '0';
 154     out << hour;
 155
 156     if (!h_for_00 || minute != 0)
 157     {
 158         out << ':';
 159         if (minute >= 0 && minute < 10)
 160             out << '0';
 161         out << minute;
 162     }
 163     else
 164         out << 'h';
 165
 166     return out.str();
 167 }
 168
 169 void WEEK::set(const std::string& daystring)
 170 {
 171     int len=daystring.length();
 172     for (int p=0; p < len; p++)
 173     {
 174         char nr[2];
 175         nr[0]=daystring[p];
 176         nr[1]=0;
 177         istringstream c(nr);
 178         int wnr=-1;
 179         if (!(c >> wnr) || wnr<0 || wnr >6)
 180             throw range_error("illegal weekday >"+string(nr)+"< in "+daystring);
 181
 182         days.set(wnr);
 183     }
 184 }
 185
 186 std::string WEEK::get_daystring() const
 187 {
 188     ostringstream out;
 189     for (int i = 0; i < 7; i++)
 190         if (days[i])
 191             out << i;
 192
 193     return out.str();
 194 }
 195
 196 std::string WEEK::get_displaystring() const
 197 {
 198     string weekdays_str;
 199
 200     // From Monday to Saturday
 201     int j;
 202     for (int i = 1; i < 7; i++)
 203     {
 204         if (days[i])
 205         {
 206             if (!weekdays_str.empty())
 207                 weekdays_str += ", ";
 208
 209             weekdays_str += get_day_display(static_cast<WEEKDAY>(i));
 210
 211             // check if we can group two or more days
 212             j = i;
 213             while (days[j] && j < 7)
 214                 j++;
 215             j--;
 216
 217             // Sunday end of week? j -> 7
 218             if (j-i > 0 && j == 6 && days[0])
 219                 j++;
 220
 221             if (j-i > 1)
 222             {
 223                 if (j == 7)
 224                     weekdays_str += "-" + get_day_display(SU);
 225                 else
 226                     weekdays_str += "-" + get_day_display(static_cast<WEEKDAY>(j));
 227
 228                 i = j;
 229             }
 230         }
 231     }
 232
 233     // special: sunday
 234     if (days[0] && j != 7)
 235     {
 236         if (!weekdays_str.empty())
 237             weekdays_str += ", ";
 238
 239         weekdays_str += get_day_display(SU);
 240     }
 241
 242     return weekdays_str;
 243 }
 244
 245 std::string WEEK::get_netfilterstring() const
 246 {
 247     string out;
 248     for (int i = 0; i < 7; i++)
 249         if (days[i])
 250         {
 251             if (!out.empty())
 252                 out+=",";
 253             out+=get_english_display(static_cast<WEEKDAY>(i));;
 254         }
 255
 256     return out;
 257 }
 258
 259 std::string WEEK::get_day_display(WEEKDAY day)
 260 {
 261     string weekday_str;
 262
 263     switch (day) {
 264         case MO:
 265             weekday_str = i18n("Mon");
 266             break;
 267         case TU:
 268             weekday_str = i18n("Tue");
 269             break;
 270         case WE:
 271             weekday_str = i18n("Wed");
 272             break;
 273         case TH:
 274             weekday_str = i18n("Thu");
 275             break;
 276         case FR:
 277             weekday_str = i18n("Fri");
 278             break;
 279         case SA:
 280             weekday_str = i18n("Sat");
 281             break;
 282         case SU:
 283             weekday_str = i18n("Sun");
 284             break;
 285         default:
 286             break;
 287     }
 288
 289     return weekday_str;
 290 }
 291
 292 std::string WEEK::get_english_display(WEEKDAY day)
 293 {
 294     string weekday_str;
 295
 296     switch (day) {
 297         case MO:
 298             weekday_str = "Mon";
 299             break;
 300         case TU:
 301             weekday_str = "Tue";
 302             break;
 303         case WE:
 304             weekday_str = "Wed";
 305             break;
 306         case TH:
 307             weekday_str = "Thu";
 308             break;
 309         case FR:
 310             weekday_str = "Fri";
 311             break;
 312         case SA:
 313             weekday_str = "Sat";
 314             break;
 315         case SU:
 316             weekday_str = "Sun";
 317             break;
 318         default:
 319             break;
 320     }
 321
 322     return weekday_str;
 323 }
 324
 325 string get_month_name(unsigned char month)
 326 {
 327     string rtn;
 328     switch(month) {
 329         case 1:
 330             rtn = i18n("January");
 331             break;
 332         case 2:
 333             rtn = i18n("February");
 334             break;
 335         case 3:
 336             rtn = i18n("March");
 337             break;
 338         case 4:
 339             rtn = i18n("April");
 340             break;
 341         case 5:
 342             rtn = i18n("May");
 343             break;
 344         case 6:
 345             rtn = i18n("June");
 346             break;
 347         case 7:
 348             rtn = i18n("July");
 349             break;
 350         case 8:
 351             rtn = i18n("August");
 352             break;
 353         case 9:
 354             rtn = i18n("September");
 355             break;
 356         case 10:
 357             rtn = i18n("October");
 358             break;
 359         case 11:
 360             rtn = i18n("November");
 361             break;
 362         case 12:
 363             rtn = i18n("December");
 364             break;
 365         default:
 366             {
 367                 ostringstream out;
 368                 out << i18n("Illegal month:") << " " << month;
 369                 rtn = out.str();
 370             }
 371     }
 372
 373     return rtn;
 374 }
 375
 376
 377 /*
 378 ** implementaion of Interval
 379 */
 380
 381
 382 /**
 383  * @brief clears the interval (make it empty).
 384  */
 385 void Interval::clear()
 386 {
 387     m_lower_bound = m_upper_bound = 0;
 388 } // eo Interval::clear()
 389
 390
 391 /**
 392  * @brief tests if there is some overlapping with another interval
 393  * @param other the other interval
 394  * @return @a true if the two intervals have a non empty intersection.
 395  */
 396 bool Interval::intersects(const Interval& other) const
 397 {
 398     return
 399         //  // other start within this:
 400         (other.m_lower_bound >= m_lower_bound and other.m_lower_bound < m_upper_bound )
 401         // // other end within this:
 402         or (other.m_upper_bound > m_lower_bound and other.m_upper_bound <= m_upper_bound )
 403         //  // other contains this
 404         or (other.m_lower_bound <= m_lower_bound and other.m_upper_bound >= m_upper_bound )
 405     ;
 406 } // eo Interval::intersects(const Interval&)
 407
 408
 409 /**
 410  * @brief tests if the current interval (fully) contains another one.
 411  * @param other the other interval.
 412  * @return @a true if the current interval fully contains the other interval.
 413  */
 414 bool Interval::contains(const Interval& other) const
 415 {
 416     return  (other.m_lower_bound >= m_lower_bound)
 417         and (other.m_upper_bound <= m_upper_bound)
 418     ;
 419 } // eo Interval::contains(const Interval& other) const
 420
 421
 422 /*
 423 ** implementation of Intervals:
 424 */
 425
 426
 427 Intervals::Intervals()
 428 {
 429 } // eo Intervals::Intervals
 430
 431
 432 void Intervals::clear()
 433 {
 434     m_intervals.clear();
 435 } // eo Intervals::clear()
 436
 437 /**
 438  * @brief tests if one of the intervals of the list intersects with the given interval.
 439  * @param other the interval to check for intersection.
 440  * @return @a true if there is an intersection.
 441  */
 442 bool Intervals::intersects(const Interval& other) const
 443 {
 444     for(const_iterator it= begin();
 445         it != end();
 446         ++it)
 447     {
 448         if ( it->intersects(other) )
 449         {
 450             return true;
 451         }
 452     }
 453     return false;
 454 } // eo Intervals::intersects(const Interval&) const
 455
 456
 457 /**
 458  * @brief tests if we have at least one intersection with another Intervals instance.
 459  * @param other the other instance.
 460  * @return @a true if there is an intersection.
 461  */
 462 bool Intervals::intersects(const Intervals& other) const
 463 {
 464     for(const_iterator it= begin();
 465         it != end();
 466         ++it)
 467     {
 468         if ( other.intersects( *it ) )
 469         {
 470             return true;
 471         }
 472     }
 473     return false;
 474 } // eo Intervals::intersects(const Intervals&) const
 475
 476
 477 /**
 478  * @brief adds a new interval to the list.
 479  * @param new_frame the new interval.
 480  *
 481  * Adds the interval to the list and joins overlapping intervals.
 482  *
 483  * @internal complexity O(n).
 484  */
 485 void Intervals::add(const Interval& new_frame)
 486 {
 487     if (not new_frame.is_valid() or new_frame.empty())
 488     {
 489         // well... we will not insert invalid or empty frames!
 490         return;
 491     }
 492     for (IntervalList::iterator it= m_intervals.begin();
 493          it != m_intervals.end();
 494          ++it)
 495     {
 496         Interval& current_frame = *it;
 497         if ( new_frame.m_lower_bound > current_frame.m_upper_bound )
 498         {
 499             // new_frame begins later than current end; go on:
 500             continue;
 501         }
 502         // at this point: the begin of the new frame is less then the current end.
 503         // now let's determine how we can insert the new frame:
 504
 505         if ( new_frame.m_upper_bound < current_frame.m_lower_bound )
 506         {
 507             // new disjoint frame; insert it before the current frame:
 508             m_intervals.insert( it, new_frame );
 509             // and we are done.
 510             return;
 511         }
 512         // at this point: the end of the new frame is >= current begin.
 513         if ( new_frame.m_upper_bound <= current_frame.m_upper_bound )
 514         {
 515             // the end of the new frame is within our current frame; we need to combine
 516             if (new_frame.m_lower_bound < current_frame.m_lower_bound)
 517             {
 518                 // the new interval starts earlier; we need to adjust our current frame:
 519                 current_frame.m_lower_bound = new_frame.m_lower_bound;
 520                 current_frame.m_changed = true;
 521             }
 522             // NOTE no "else" part needed since in that case our current frame already
 523             // contains the new one!
 524
 525             // we are done:
 526             return;
 527         }
 528         // at this point: end of new frame > end of current frame
 529         // so we need to extend the current frame; at least the end.
 530         // But we need to deal with intersects of following frames... *sigh*
 531
 532         // first the simple part: let's see if we need to move the start:
 533         if ( new_frame.m_lower_bound < current_frame.m_lower_bound)
 534         {
 535             // yes, we need to move the start:
 536             current_frame.m_lower_bound = new_frame.m_lower_bound;
 537             current_frame.m_changed= true;
 538         }
 539
 540         // now let's extend the end:
 541         current_frame.m_upper_bound = new_frame.m_upper_bound;
 542         current_frame.m_changed = true;
 543
 544         // well... let's walk through the following frames; looking for more joins...:
 545         IntervalList::iterator it2 = it;
 546         while(      ++(it2=it) != m_intervals.end()
 547                 and current_frame.m_upper_bound >= it2->m_lower_bound
 548            )
 549         {
 550             Interval next_frame= *it2;
 551             if ( current_frame.m_upper_bound < next_frame.m_upper_bound )
 552             {
 553                 // in this case our end is within the next frame.
 554                 // adjust our end.
 555                 current_frame.m_upper_bound = next_frame.m_upper_bound;
 556             }
 557             // and remove the next frame since the current frame contains it (now):
 558             m_intervals.erase(it2);
 559         }
 560         // we are done!
 561         return;
 562     }
 563     // at this point: new frame starts later than the last frame ends
 564     // append the new frame:
 565     m_intervals.push_back( new_frame );
 566 } // eo Intervals::add(const Interval&)
 567
 568
 569 /**
 570  * @brief subtracts a time interval from the list.
 571  * @param del_frame the time interval to subtract.
 572  *
 573  * removes the time interval from the list; cut off parts from or remove existing
 574  * intervals if they overlap.
 575  *
 576  * @internal complexity O(n).
 577  */
 578 void Intervals::sub(const Interval& del_frame)
 579 {
 580     if (not del_frame.is_valid() or del_frame.empty() )
 581     {
 582         return;
 583     }
 584     for (IntervalList::iterator it= m_intervals.begin();
 585          it != m_intervals.end();
 586          )
 587     {
 588         Interval& current_frame = *it;
 589         if ( del_frame.m_lower_bound >= current_frame.m_upper_bound )
 590         {
 591             // del_frame begins later than current end; go on:
 592             ++it;
 593             continue;
 594         }
 595         // at this point: the begin of the del frame is less then the current end.
 596         if ( del_frame.m_upper_bound < current_frame.m_lower_bound )
 597         {
 598             // end is before our start; nothing to do.
 599             return;
 600         }
 601         // at this point: the end of the del frame is >= current begin.
 602         if ( del_frame.m_upper_bound < current_frame.m_upper_bound )
 603         {
 604             // del frame end point is within our interval.
 605             if ( del_frame.m_lower_bound > current_frame.m_lower_bound)
 606             {
 607                 // the del frame is within our interval... we need to split:
 608                 m_intervals.insert(it, Interval( current_frame.m_lower_bound, del_frame.m_lower_bound ) );
 609             }
 610             // adjust start of current frame:
 611             if (current_frame.m_lower_bound < del_frame.m_upper_bound)
 612             {
 613                 current_frame.m_lower_bound= del_frame.m_upper_bound;
 614                 current_frame.m_changed= true;
 615             }
 616             // and we are done!
 617             return;
 618         }
 619         // at this point the end of the del frame is >= current end
 620         if ( del_frame.m_lower_bound > current_frame.m_lower_bound )
 621         {
 622             // a part of the current interval needs to be preserved..
 623             // move the end.
 624             current_frame.m_upper_bound= del_frame.m_lower_bound;
 625             current_frame.m_changed= true;
 626             // and continue with the next interval:
 627             ++it;
 628             continue;
 629         }
 630         // at this point; the whole frame needs to be deleted..
 631         if ( it == m_intervals.begin())
 632         {
 633             m_intervals.erase(it);
 634             it= m_intervals.begin();
 635         }
 636         else
 637         {
 638             IntervalList::iterator it2= it++;
 639             m_intervals.erase(it2);
 640         }
 641     }
 642 } // eo Intervals::sub(const Interval&)
 643
 644
 645 /**
 646  * @brief returns if we contain an interval.
 647  * @param other the interval to check.
 648  * @return @a true if we cover the given interval, too.
 649  */
 650 bool Intervals::contains(const Interval& other) const
 651 {
 652     for(const_iterator it= begin();
 653         it != end();
 654         ++it)
 655     {
 656         if ( it->contains( other ))
 657         {
 658             return true;
 659         }
 660     }
 661     return false;
 662 } // eo Intervals::contains(const Interval&) const
 663
 664
 665 /**
 666  * @brief returns if we contain an exact interval.
 667  * @param other the interval to check.
 668  * @return @a true if we axactly contains the given interval.
 669  *
 670  * @note thsi differs from contain in the way, that we return only @a true
 671  * iff we have the given interval in our list; not only cover it.
 672  */
 673 bool Intervals::contains_exact(const Interval& other) const
 674 {
 675     for(const_iterator it= begin();
 676         it != end();
 677         ++it)
 678     {
 679         if ( *it == other)
 680         {
 681             return true;
 682         }
 683     }
 684     return false;
 685 } // eo Intervals::contains_exact(const Interval&)const
 686
 687
 688 /**
 689  * @brief returns if we contain another interval combination.
 690  * @param other the intervals to check.
 691  * @return @a true if we cover the given intervals, too.
 692  *
 693  * @internal we rely on the fact that the lists are sorted and contain
 694  * disjoint intervals.
 695  *
 696  * So this method has a complexity of O(n).
 697  */
 698 bool Intervals::contains(const Intervals& other) const
 699 {
 700     const_iterator my_it= begin();
 701     const_iterator other_it= other.begin();
 702     while( my_it != end() and other_it!= other.end() )
 703     {
 704         // seek the first interval which contains the lower bound of the current other interval
 705         while (my_it != end()
 706                and my_it->m_lower_bound > other_it->m_lower_bound
 707                and other_it->m_lower_bound >= my_it->m_upper_bound
 708               )
 709         {
 710             ++my_it;
 711         }
 712         if (my_it == end())
 713         {
 714             break;
 715         }
 716         if (not my_it->contains( *other_it ))
 717         {
 718             // if we don't contain the current other; we're done:
 719             return false;
 720         }
 721         //else check the next other interval:
 722         ++other_it;
 723     }
 724     return (other_it == other.end());
 725 } // eo Intervals::contains(const Intervals&) const
 726
 727
 728 /**
 729  * @brief combines to interval combinates for equality
 730  * @param other the other instance.
 731  * @return @a true if the other is equal to the current.
 732  *
 733  * @internal since the lists are sorted, we compare the interval lists.
 734  * Thus we have a complexity of O(n).
 735  */
 736 bool Intervals::operator==(const Intervals& other) const
 737 {
 738     // since we keep sorted lists: just compare the lists :-)
 739     return m_intervals == other.m_intervals;
 740 } // eo Intervals::operator==(const Intervals&)
 741
 742
 743 Intervals& Intervals::operator+=(const Interval& other)
 744 {
 745     add(other);
 746     return *this;
 747 } // eo operator+=(const Interval&)
 748
 749
 750 Intervals& Intervals::operator-=(const Interval& other)
 751 {
 752     sub(other);
 753     return *this;
 754 } // eo operator-=(const Interval&)
 755
 756
 757 /**
 758  * @brief adds the intervals of a second instance to us.
 759  * @param other the other instance.
 760  * @return self reference (allow chaining).
 761  *
 762  * @internal since we do simple loops over the other and our intervals
 763  * we have a complexity of O(n^2).
 764  *
 765  * @todo optimize if complexity becomes a problem.
 766  */
 767 Intervals& Intervals::operator+=(const Intervals& other)
 768 {
 769     for(const_iterator it= other.begin();
 770         it != other.end();
 771         ++it)
 772     {
 773         add( *it );
 774     }
 775     return *this;
 776 } // eo operator+=(const Intervals&)
 777
 778
 779 /**
 780  * @brief subtracts the intervals of a second instance from us.
 781  * @param other the other instance.
 782  * @return self reference (allow chaining).
 783  *
 784  * @internal since we do simple loops over the other and our intervals
 785  * we have a complexity of O(n^2).
 786  *
 787  * @todo optimize if complexity becomes a problem.
 788  */
 789 Intervals& Intervals::operator-=(const Intervals& other)
 790 {
 791     if (&other == this)
 792     {
 793         m_intervals.clear();
 794     }
 795     else
 796     {
 797         for(const_iterator it= other.begin();
 798             it != other.end();
 799             ++it)
 800         {
 801             sub( *it );
 802         }
 803     }
 804     return *this;
 805 } // eo operator-=(const Intervals&)
 806
 807
 808
 809 /*
 810 ** clock funcs:
 811 */
 812
 813
 814 /**
 815  * @brief fetches the value from the monotonic clock source.
 816  * @param[out] seconds the seconds.
 817  * @param[out] nano_seconds the nano seconds.
 818  * @return @a true if the clock was successfully read.
 819  */
 820 bool monotonic_clock_gettime(long int& seconds, long int& nano_seconds)
 821 {
 822     struct timespec tp[1];
 823     int res= ::syscall(__NR_clock_gettime, CLOCK_MONOTONIC, tp);
 824     if (0 == res)
 825     {
 826         seconds= tp->tv_sec;
 827         nano_seconds= tp->tv_nsec;
 828     }
 829     return (res==0);
 830 } // eo monotonic_clock_gettime(long int&,long int&)
 831
 832
 833 /**
 834  * @brief fetches the value from the monotonic clock source.
 835  * @return the time since system start in nanoseconds, 0 if read was unsuccessful
 836  */
 837 long long monotonic_clock_gettime_nano()
 838 {
 839     long int seconds;
 840     long int nano_seconds;
 841     long long nano=0;
 842
 843     if (monotonic_clock_gettime(seconds,nano_seconds))
 844     {
 845         nano=seconds;
 846         nano*=1000000000LL;
 847         nano+=nano_seconds;
 848     }
 849
 850     return nano;
 851 }
 852
 853 /**
 854  * @brief fetches the value from the monotonic clock source.
 855  * @param[out] seconds the seconds.
 856  * @param[out] nano_seconds the nano seconds.
 857  * @return @a true if the clock was successfully read.
 858  */
 859 bool realtime_clock_gettime(long int& seconds, long int& nano_seconds)
 860 {
 861     struct timespec tp[1];
 862     int res= ::syscall(__NR_clock_gettime, CLOCK_REALTIME, tp);
 863     if (0 == res)
 864     {
 865         seconds= tp->tv_sec;
 866         nano_seconds= tp->tv_nsec;
 867     }
 868     return (res==0);
 869 } // eo realtime_clock_gettime(long int&,long int&)
 870
 871